8320번: 직사각형을 만드는 방법
상근이는 변의 길이가 1인 정사각형 n개를 가지고 있다. 이 정사각형을 이용해서 만들 수 있는 직사각형의 개수는 총 몇 개일까? 두 직사각형 A와 B가 있을 때, A를 이동, 회전시켜서 B를 만들 수
www.acmicpc.net
길이가 1인 정사각형 N개를 가지고 만들 수 있는 직사각형의 갯수를 구하는 문제입니다.
이 때, N개를 모두 사용하지 않아도 됩니다.
저는 N개로 만들 수 있는 높이(i)가 1인 직사각형부터 높이를 1씩 늘려가며 갯수를 구하였습니다.
그럼 너비(j)는 i * j <= N 인 경우의 갯수를 세어주시면 됩니다.
N = 6일 때를 예로 들면
높이가 1일 때 가능한 너비 => 1, 2, 3, 4, 5, 6
높이가 2일 때 가능한 너비 => 1, 2, 3
높이가 3일 때 가능한 너비 => 1, 2
높이가 4일 때 가능한 너비 => 1
높이가 5일 때 가능한 너비 => 1
높이가 6일 때 가능한 너비 => 1
답 14??
이렇게 구할수 있지만 문제에는 직사각형 A를 회전시켜서 B를 만들 수 있는 경우
즉, (i * j)이나 (j * i)이나 같은 직사각형으로 본다는 것입니다. 그러면 중복체크를 해야합니다.
그러면
높이가 1일 때 가능한 너비 => 1, 2, 3, 4, 5, 6
높이가 2일 때 가능한 너비 => 2, 3
답 8
이렇게 축소를 시킬 수 있습니다.
여기서 찾은 규칙성이 높이는 1부터 sqrt(N)까지, 너비는 i부터 i * j <= N까지임을 알 수 있습니다.
|
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
|
#include <iostream>
#include <cmath>
using namespace std;
int N;
void func() {
int ans = 0;
for (int i = 1; i <= sqrt(N); i++) {
for (int j = i; i * j <= N; j++) {
ans++;
}
}
cout << ans << '\n';
}
int main() {
cin.tie(NULL); cout.tie(NULL);
ios::sync_with_stdio(false);
cin >> N;
func();
return 0;
}
|
cs |
'algorithm > Implementation' 카테고리의 다른 글
| boj 16719 ZOAC (0) | 2021.03.15 |
|---|---|
| boj 3085 사탕 게임 (0) | 2021.02.26 |
| boj 3985 롤 케이크 (0) | 2021.02.25 |
| boj 2116 주사위 쌓기 (0) | 2021.02.25 |
| boj 10163 색종이 (0) | 2021.02.24 |