[BOJ] 6359. 만취한 상범

https://www.acmicpc.net/problem/6359

6359번: 만취한 상범

먼저 상범이는 첫 번째 라운드에서 모든 방의 문을 열고, 그다음 라운드부터는 

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인 값들(열려있는 방)의 개수를 구해주면 된다.

#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;
}