[Programmers] #42842 - 카펫 [Java][C++][Python]
[Programmers] #42842 - 카펫 [Java][C++][Python]
1. 아이디어
갈색과 노란색 격자 수로 카펫의 가로와 세로를 구하는 문제로, 카펫의 가로를 $w$, 세로를 $h$라 하면 갈색은 테두리 한 줄이라 $2w + 2h - 4$개이고 노란색은 그 안쪽이라 $(w - 2)(h - 2)$개이다. 갈색 격자 수로 $w + h$가 정해지므로 세로를 하나 고르면 가로도 정해지고, 그때 안쪽 격자 수가 노란색 격자 수와 같은지만 확인하면 된다.
세로는 노란색이 1개 이상이라 3부터 시도하면 된다. $w + h$와 $(w - 2)(h - 2)$가 정해지면 $w - 2$와 $h - 2$는 합과 곱이 정해진 두 수라 순서만 빼고 하나로 정해진다. 그래서 세로를 작은 것부터 보면 처음 맞는 쌍이 가로가 세로 이상인 답이다. 갈색 격자가 5,000개 이하라 세로를 하나씩 모두 시도해도 충분하다.
2. 코드
풀이 [Java][C++][Python]
1
2
3
4
5
6
7
8
9
10
class Solution {
public int[] solution(int brown, int yellow) {
for (int h = 3; h < brown; h++) {
int w = (brown + 4) / 2 - h;
if ((w - 2) * (h - 2) == yellow) return new int[]{w, h};
}
return null;
}
}
1
2
3
4
5
6
7
8
9
10
11
#include <bits/stdc++.h>
using namespace std;
vector<int> solution(int brown, int yellow) {
for (int h = 3; h < brown; h++) {
int w = (brown + 4) / 2 - h;
if ((w - 2) * (h - 2) == yellow) return {w, h};
}
return {};
}
1
2
3
4
5
def solution(brown, yellow):
for h in range(3, brown):
w = (brown + 4) // 2 - h
if (w - 2) * (h - 2) == yellow:
return [w, h]
This post is licensed under CC BY 4.0 by the author.