문제
강의에 들어있는 문제라서 문제 링크를 걸어도 되는지 모르겠다.
한칸의 길이가 1인 정사각형들로 이루어진 직사각형이 있다.
테두리 칸들은 갈색, 그 외는 빨간색으로 칠해져 있다.
갈색과 빨간색 칸의 개수가 주어졌을때, 직사각형의 가로, 세로 크기를 구하자
갈색 격자 : brown
빨간색 격자 : red
8 <= brown <= 5,000
1 <= red <= 2,000,000
카펫의 가로 길이는 세로 길이보다 크거나 같다.
입출력 예시
| brown | red | return |
|---|---|---|
| 10 | 2 | [4,3] |
| 8 | 1 | [3,3] |
| 24 | 24 | [8,6] |
접근
우선, \(brown + red = 직사각형의 넓이\) 라는 것을 알 수 있다.
또한 빨간 격자가 한개 이상 존재한다.
즉, 가로, 세로 길이가 최소 3이상이다.
카펫의 가로, 세로를 \(w, h\) 라고 했을 때, 빨간 격자의 개수는 \((w-2) * (h-2)\) 이고,
\((w-2) * (h-2) = red\) 를 만족하는 쌍을 찾으면 될 것이다.
이 때 카펫의 최대 넓이는 약 200만 정도이고, 오래걸려도 \(\sqrt{2000000}\) 번 안에 찾을 것이다.
코드
- 파이썬 코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
def solution(brown, red):
answer = []
sum = brown + red
start_i = 3
while True:
h = divisor_number(sum, start_i)
start_i += 1
if h == -1:
continue
w = sum / h
if w > 2 and h > 2:
r = (w-2) * (h-2)
if red == r:
answer.append(w)
answer.append(h)
break
return answer
def divisor_number(num, start_i):
for i in range(start_i, num):
if num % i == 0:
return i
return -1
- C++ 코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include <vector>
using namespace std;
vector<int> solution(int brown, int yellow) {
vector<int> answer;
int sum = brown + yellow;
int start_i = 3;
while(true){
int h = -1;
for(int i = start_i; i<sum;i++){
if(sum%i==0){
h = i;
break;
}
}
start_i++;
if(h==-1)
continue;
int w = sum/h;
if (w>2 && h>2){
int r = (w-2)*(h-2);
if (yellow == r){
answer.push_back(w);
answer.push_back(h);
break;
}
}
}
return answer;
}