https://www.acmicpc.net/problem/6359
6359번: 만취한 상범
문제 서강대학교 곤자가 기숙사의 지하에는 n개의 방이 일렬로 늘어선 감옥이 있다. 각 방에는 벌점을 많이 받은 학생이 구금되어있다. 그러던 어느 날, 감옥 간수인 상범이는 지루한 나머지 정신나간 게임을 하기로 결정했다. 게임의 첫 번째 라운드에서 상범이는 위스키를 한 잔 들이키고, 달려가며 감옥을 한 개씩 모두 연다. 그 다음 라운드에서는 2, 4, 6, ... 번 방을 다시 잠그고, 세 번째 라운드에서는 3, 6, 9, ... 번 방이 열려있으면 잠그고
www.acmicpc.net
먼저 상범이는 첫 번째 라운드에서 모든 방의 문을 열고, 그다음 라운드부터는
k번째 라운드에서는 번호가 k의 배수인 방이 열려 있으면 잠그고, 잠겨 있다면 연다.
이런 식으로 n번째 라운드까지 진행한다.
문제의 입력으로 테스트 케이스와 함께 n값이 주어진다. n값은 방의 개수이자 라운드 진행 수이다.
이 문제는 2번째 라운드에서 2의 배수인 방들은 문이 잠겨져 있고 나머지 방들은 열려있는 상태에서
3번째 라운드를 진행한다.
즉, i번째 라운드의 상태에서 i+1번째 라운드의 상태로 바뀌므로 DP(Dynamic Programming)로 해결할 수 있다.
n(5 ≤ n ≤ 100)
n의 범위가 위와 같으므로 n이 100인 경우까지 모두 미리 구해놓으면 된다.
DP 식은 다음과 같이 정의할 수 있다.
dp[i][j] = true (i번째라운드의 j번 방이 열려있다)
dp[i][j] = false (i번째라운드의 j번 방이 잠겨져 있다)
위의 식을 이용하여 1번째라운드부터 n번째라운드까지 순차적으로 구할 수 있다.
dp배열을 모두 구해놨다면 n이 주어졌을 때, dp[n][i] (1<= i <= n) 중 true인 값들(열려있는 방)의 개수를 구해주면 된다.
|
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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
|
#include<iostream>
#include <cstring>
using namespace std;
bool d[101][101];
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
//열리면 true 잠기면 false
//1번째 라운드에서 모든 방을 연다. (true로 초기화)
memset(d[1], true, sizeof(d[1]));
//i번째 라운드에서 j번 방 문을 열거나 잠근다.
for (int i = 2; i <= 100; i++) {
//이전 방 문의 상태를 복사
for (int j = 1; j <= 100; j++) {
d[i][j] = d[i - 1][j];
}
//i의 배수인 방 문만 열거나 잠근다.
for (int j = i; j <= 100; j += i) {
if (d[i - 1][j]) d[i][j] = false;
else d[i][j] = true;
}
}
int T;
cin >> T;
int n;
while (T--) {
cin >> n;
int cnt = 0;
for (int i = 1; i <= n; i++) {
//문이 열려있다
if (d[n][i]) cnt++;
}
cout << cnt << '\n';
}
return 0;
}
Colored by Color Scripter
|
'BOJ' 카테고리의 다른 글
| [BOJ] 17471. 게리맨더링 (0) | 2019.10.16 |
|---|---|
| [BOJ] 17141. 연구소 2 (0) | 2019.09.06 |
| [BOJ] 1931. 회의실배정 (0) | 2019.09.02 |
| [BOJ] 2217. 로프 (0) | 2019.09.02 |
| [BOJ] 1541. 잃어버린 괄호 (0) | 2019.09.02 |