[프로그래머스] 완전탐색 - 카펫 (Java)

프로그래머스 Level 2  완전탐색 - 카펫 (자바)

출처

programmers.co.kr/learn/courses/30/lessons/42842

코딩테스트 연습 - 카펫

 

 

 

문제

Leo는 카펫을 사러 갔다가 아래 그림과 같이 중앙에는 노란색으로 칠해져 있고 테두리 1줄은 갈색으로 칠해져 있는 격자 모양 카펫을 봤습니다.

문제 예시 1

Leo는 집으로 돌아와서 아까 본 카펫의 노란색과 갈색으로 색칠된 격자의 개수는 기억했지만, 전체 카펫의 크기는 기억하지 못했습니다.

Leo가 본 카펫에서 갈색 격자의 수 brown, 노란색 격자의 수 yellow가 매개변수로 주어질 때 카펫의 가로, 세로 크기를 순서대로 배열에 담아 return 하도록 solution 함수를 작성해주세요.

 

 

 

제한사항

• 갈색 격자의 수 brown은 8 이상 5,000 이하인 자연수입니다.
• 노란색 격자의 수 yellow는 1 이상 2,000,000 이하인 자연수입니다.
• 카펫의 가로 길이는 세로 길이와 같거나, 세로 길이보다 깁니다.

 

 

 

입출력 예

입출력 예 1

 

 

 

접근 방법

* 완전탐색이 아니라 이 문제는 수학적 지식을 요구한다...

1. brown 블록은 테두리 1칸을 모두 차지한다는 것을 파악 -> 테두리와 같다.

2. 둘레(brown)는 2*n(가로) + 2*(m-2)이다. (-2 이유는 위, 아래 1칸씩 겹치기 때문)

3. 위 수식을 변형하면 m+n = (brown+4)/2

4. 예시를 기준으로 (n-2) * (m-2) == yellow 이다.

위 조건들에 해당하면 answer에 넣어준다. 

 

 

 

내 코드

class Solution {
    public int[] solution(int brown, int yellow) {
        int[] answer = new int[2];
        
        //가로 최대 = ?
        //세로 최대 = ?
        //가로 >= 세로
        
        //둘레 = 2*n + 2*(m-2) == brown -> m + n = (brown + 4)/2
        
        //yellow = (n-2) * (m-2)
        
        //둘레
        int size = (brown+4) / 2;
        //세로
        int m = 3;
        //가로
        int n = size - m;
        
        while (n >= 3 && n >= m) {
            if ((n-2) * (m-2) == yellow) {
                answer[0] = n;
                answer[1] = m;
                break;
            }
            n--;
            m++;
        }
        
        return answer;
    }
    
}

 

 

고려할 점

1. 수학적 해결법 생각

2. 둘레와 yellow 등 접근방법 파악