프로그래머스 -[카펫] 42842

문제링크

코딩테스트 연습 - 카펫 | 프로그래머스 (programmers.co.kr)

코딩테스트 연습 - 카펫

 

갈색, 노란색 격자의 갯수가 주어졌을 때 전체 카펫의 가로, 세로의 길이를 구하는 문제입니다.

 

 

keypoint

모든 각 격자의 넓이를 1로 생각.

카펫 가로 길이: m

세로 길이 : n 일 때

m, n, yellow, brown 으로 식을 세운 뒤, 가능한 모든 순서쌍을 탐색한다. (완전탐색)

완전 탐색을 할 때 for문에서 변수의 범위를 잘 정해야 한다는 것이다. 이는 여러 조건에서 추론할 수 있다.

 

 

풀이

갈색 격자는 카펫의 겉테두리 부분으로, 그 두께는 1입니다. 나머지 속 부분은 모두 노란색으로 채워져 있습니다.

따라서 (m+n)x2 = brown+4 가 됩니다. 

또한 m x n = 카펫의 넓이 (=yellow + brown) 입니다. 따라서 다음과 같이 2가지 식을 쓸 수 있습니다.

m+n = (brown+4)/2;
m*n = yellow + brown;

 

문제의 조건에서, 가로의 길이가 세로 길이보다 크다고 했으므로, m>=n 입니다.

또 brown은 8이상, yellow는 1이상이라고 명시되어 있으므로 카펫의 가로, 세로 길이는 3이상입니다.  m, n >= 3

m >= n;
m, n >= 3

 

따라서 우리는 위 식을 만족하고, 범위를 정해 m,n 을 완전탐색하여 찾으면 됩니다.

3 <= n <= (brown+4)/4

3 <= m <= (brown+4)/2 -3

for(int i=3;i<=(brown+4)/4;i++){ // n
    for(int j=3;j<=(brown+4)/2-3;j++){ // m
        if(i+j == (brown+4)/2 && i*j==yellow + brown){
            n=i; m=j;
        }
    }
}

완전탐색하여 m ,n 값을 찾으면 정답입니다.

 

 

소스코드

public int[] solution(int brown, int yellow) {
        int[] answer = new int[]{0,0};
        int m=0,n=0; // n:세로, m:가로

//        m+n = (brown+4)/2;
//        m*n = yellow + brown;

        for(int i=3;i<=(brown+4)/4;i++){ // n
            for(int j=3;j<=(brown+4)/2-3;j++){ // m
                if(i+j == (brown+4)/2 && i*j==yellow + brown){
                    n=i; m=j;
                }
            }
        }

        answer[0] = m;
        answer[1] = n;

        return answer;
    }