[프로그래머스] 카펫(java)

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

코딩테스트 연습 - 카펫

어떻게 생각하고 문제를 풀었는가?

테두리 1줄이 갈색으로 칠해져 있으므로 갈색 타일의 수는 (가로줄+세로줄)x2-4로서 확인할 수 있습니다.

또한 전체 타일은 가로줄 x 세로줄이며 갈색 타일과 노란색 타일의 합으로 이루어져 있으므로 두 식을 이용하여 가로줄과 세로줄의 조합이 올바른 조합인지 판단할 수 있습니다.

 

코드

class Solution {
    public int[] solution(int brown, int yellow) {
	int[] answer = {3,3};
        int tiles = brown+yellow;
        while((brown!=(answer[0]+answer[1])*2-4)||(tiles != answer[0]*answer[1])){
            if(answer[0]==answer[1]){
                answer[0]++;
                answer[1]=3;
            }else{
                answer[1]++;
            }
        }
        return answer;
    }
} 

완전탐색을 이용하여 작성한 코드입니다. 노란색 타일은 테두리 1줄의 갈색 타일들 안에 존재하므로 {3, 3}부터 시작하여 정답을 탐색합니다.

카펫의 가로 길이는 세로 길이보다 길어야 한다는 조건이 있기 때문에 가로길이를 늘리고, 세로길이를 3에서부터 같을 때까지 늘리는 탐색을 계속하여 정답을 찾을 수 있습니다.

 

개선

class Solution {
    public int[] solution(int brown, int yellow) {
        int total = (brown+4)/2;
        int tiles = yellow+brown;
        int[] answer = new int[2];
        answer[0] = (total + (int)Math.sqrt(total*total-4*tiles))/2;
        answer[1] = total - answer[0];
        return answer;
    }
}

 

완전 탐색에서 값을 증명하는데 사용되는 식을 반대로 값을 구하는데 사용하여 코드를 작성하였습니다.

1. 전체 타일의 수 = 가로줄*세로줄

2. 가로줄과 세로줄의 합 = (갈색 타일의 수+4)/2

이 두가지의 식으로 가로줄을 x, 세로줄을 y라 하였을 때 x+y=yellow+brown, x*y = (brown+4)/2로서 표현할 수 있습니다.

y=(전체 타일의 수)-x, x*(전체 타일의 수-x) = x^2-(전체 타일의 수)*x + (가로줄과 세로줄의 합)=0 이라는 x에 대한 이차방정식으로 표현할 수 있으며 근의 공식을 활용하여 x, y값을 도출해낼 수 있습니다.