[프로그래머스] 카펫 (자바) / 완전 탐색

문제

 

입출력

 

문제풀이

import java.util.*;
class Solution {
    public int[] solution(int brown, int yellow) {
        int[] answer = new int[2];
        // x*2+y*2=brown+4;
        // (x-2)*(y-2)=yello;
        // xy-2*x-2*y+4=yello;
        // xy=yello+brown;
        int k = yellow + brown;
        int j = 0;
        for(int i = 1 ; i <= Math.sqrt(k);i++){
            if(k%i==0){
                j = k/i;
                if(i*2+j*2-4==brown){
                    answer[0]=j;
                    answer[1]=i;
                }
            }
        }
        
        return answer;
    }
}

 

 

※ 내 생각

이 문제는 완전 탐색을 이용하는 문제입니다.

// x*2+y*2=brown+4;
// (x-2)*(y-2)=yellow;
아래 식을 풀면 xy -2*x-2*y+4=yellow;이고
위 식을 대입하여 정리하면 xy = brown + yellow가 됩니다.
for 문의 범위는 가로길이가 세로길이 보다 크고
둘다 xy의 약수 이기 때문에
제곱근의 범위를 돌리면 중복되지 않고 해결할 수 있습니다.

 

테스트 결과