프로그래머스 고득점 kit 완전탐색 분류의 Level2 문제! ( 문제 링크 )
이렇게 완전 탐색도 다 뽀갰다 ✅ !
문제 설명
Leo는 카펫을 사러 갔다가 아래 그림과 같이 중앙에는 노란색으로 칠해져 있고 테두리 1줄은 갈색으로 칠해져 있는 격자 모양 카펫을 봤습니다.
Leo는 집으로 돌아와서 아까 본 카펫의 노란색과 갈색으로 색칠된 격자의 개수는 기억했지만, 전체 카펫의 크기는 기억하지 못했습니다.
Leo가 본 카펫에서 갈색 격자의 수 brown, 노란색 격자의 수 yellow가 매개변수로 주어질 때 카펫의 가로, 세로 크기를 순서대로 배열에 담아 return 하도록 solution 함수를 작성해주세요.
제한사항
- 갈색 격자의 수 brown은 8 이상 5,000 이하인 자연수입니다.
- 노란색 격자의 수 yellow는 1 이상 2,000,000 이하인 자연수입니다.
- 카펫의 가로 길이는 세로 길이와 같거나, 세로 길이보다 깁니다.
입출력 예
| brown | yellow | return |
|---|---|---|
| 10 | 2 | [4, 3] |
| 8 | 1 | [3, 3] |
| 24 | 24 | [8, 6] |
풀이 방법
테두리에 한 줄이 갈색 타일이므로 width와 height가 있을 때 갈색 타일과 노란 타일의 수를 width와 height로 나타낼 수 있다. 그렇기 때문에 수학적으로 푸는 것이 가능할 것 같았지만 완전탐색 분류에 있기에 본인은 완전탐색으로 풀어보았다 !
나는 노란 타일의 가로 세로를 width, height로 두고 문제를 풀었다. yellow의 약수들 중에서 점점 height를 1부터 점점 늘려가며 탐색을 진행해갔다 ! 이 경우에 brown = width2 + (height+2)2 로 나타낼 수 있다. 이 것을 조건으로 점검하여 주어진 brown값과 일치하는 경우를 답으로 반환하였다 ! 가로가 세로보다 크거나 같다는 조건이 있으므로 height를 1부터 탐색해갔다.
문제는 아주 쉽다 ! 위와 반대로 brown의 개수를 기준으로 탐색하며 yellow가 주어진 값과 일치하는 경우를 찾아도 물론 가능하다. 그리고 처음에 언급한 것처럼 수학적으로 문제를 푼 사람도 많은 것 같았다 ! 다양한 방법으로 쉽게 풀어볼 수 있는 문제이다 ~
코드
class Solution {
public int[] solution(int brown, int yellow) {
int[] answer = new int[2];
int width, height;
for(int i=1; i<=yellow; i++){
if(yellow%i != 0) continue;
height = i;
width = yellow/height;
if((width*2+(height+2)*2) == brown){
answer[0] = width+2;
answer[1] = height+2;
break;
}
}
return answer;
}
}