카펫

문제 링크

문제 풀이 시간 :

문제 요약

• 중앙은 노란색, 테두리 1줄은 갈색인 격자 카펫에서 갈색 칸 수 brown, 노란색 칸 수 yellow가 주어짐
• 카펫의 가로, 세로 크기를 순서대로 배열에 담아 반환
• 가로 길이는 세로 길이와 같거나 더 김
• brown은 8 이상 5,000 이하, yellow는 1 이상 2,000,000 이하

문제 풀이

처음엔 가로, 세로 길이를 각각 1부터 전체 칸 수(brown + yellow)까지 이중 반복문으로 완전탐색하면서, 두 값을 곱해 전체 칸 수와 같은지, 그리고 (가로-2)*(세로-2)가 yellow와 같은지 확인하면 되겠다고 생각했다.

하지만 brown + yellow는 최대 2,005,000까지 갈 수 있는데, 이중 반복문으로 가로와 세로를 각각 완전탐색하면 최대 2,005,000 × 2,005,000번을 확인해야 해서 시간 안에 끝날 수 없다.

이 문제의 핵심은 가로 길이가 세로 길이보다 크거나 같으므로, 세로 길이는 항상 전체 칸 수의 제곱근 이하라는 점이다.

세로 길이 후보를 3부터 √total까지만 순회하면서 전체 칸 수를 나누어떨어지게 하는 값을 찾고, 그때의 가로 길이(total / 세로)로 갈색 칸 개수 공식이 맞는지만 확인하면 된다.

최종 코드

class Solution {
    public int[] solution(int brown, int yellow) {
        
        int total = brown+yellow;
        
        for(int w=3;w*w<=total;w++){
            if(total%w!=0)
                continue;
            
            int h = total/w;
            
            if((w-2)*(h-2) == yellow)
                return new int[]{h,w};
        }
        
        
        return new int[]{};
    }
}