https://school.programmers.co.kr/learn/courses/30/lessons/42842
풀이
분류는 완전탐색인데 푸는건 약수를 이용해서 풀었다. 완탐으로도 풀 수 있을 것 같은데 내가 푼 방식이 더 효율성이 높을 것 같다.
결국 카펫을 이루는 것은 노란색으로 이루어진 판을 갈색으로 한 칸씩 감싸는 것이기 때문에, 노란색이 어떻게 이루어져 있는지 결정하고 가로/세로로 +2씩만 하면 카펫이 구성되는 것을 이용한다.
코드
class Solution {
public int[] solution(int brown, int yellow) {
int[] answer = new int[2];
int width = 0, depth = 0;
for (int i = 1; i <= yellow; i++) {
if (yellow % i == 0) {
//yellow가 어떤 모양일지를 yellow의 약수로 구한다.
//이 때 가로 >= 세로 이므로 yellow를 이루는 두 수중 큰게 가로.
width = Math.max(i, yellow / i);
depth = Math.min(i, yellow / i);
//노란색의 가로, 세로에 양끝에 2개씩 붙인게 총 카펫의 개수
if ((width + 2) * (depth + 2) == brown + yellow) {
answer[0] = width + 2;
answer[1] = depth + 2;
break;
}
}
}
return answer;
}
}
'Problem Set > 구현' 카테고리의 다른 글
[BOJ] 1986. 체스 (0) | 2023.10.01 |
---|