6359번 : 만취한 상범

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

6359번: 만취한 상범

 

 

이 문제도 DP를 잘 정의하면 쉽게 풀 수 있다.

 

 

동적 계획법에서 항상 메모이제이션이 필요한 것은 아니다.

 

 

---

 

 

자, DP를 만약에 현재 라운드에서 탈출할 수 있는 사람의 수로 정의할 수 있을까?

 

 

 

R= 현재라운드

 

 

 

DP[R], DP[R - 1] 관계식을 세울 수 없다.

 

 

따라서, 뭔가 변수가 더 필요하다고 판단했다.

 

 

 

B = 방 번호

 

 

 

DP[B][R] = 방 번호가 B인 방에서, R 라운드에 문 열림의 유무

 

 

 

이렇게 되면, 재귀적으로 구성할 수 있다.

 

 

 

1) B가 R로 나누어 떨어질 때

- 이전 라운드에서 방문이 열려있다면, 닫기

- 이전 라운드에서 방문이 닫혀있다면 열기

 

 

2) B가 R로 나누어 떨어지지 않을 때

- 이전 라운드 방문을 그대로 나두기

 

 

 

자, 하향식 접근으로 문제를 풀었다. 상향식으로 풀면 더 쉬울 거 같긴하다.

 

 

 

---

 

 

해설코드(C++).

 

 

 

#include <iostream>
#include <algorithm>
#include <cstring>
 
using namespace std;
 
int solve(int round, int Room) {
    if (round == 1)
        return 0;
 
    if (Room % round == 0) {
        if (solve(round - 1, Room) == 1) {
            return 0;
        }
        else {
            return 1;
        }
    }
    else {
        return solve(round - 1, Room);
    } 
}
 
int T, N;
 
int main(void) {
    freopen("input.txt", "r", stdin);
    cin >> T;
    for (int i = 0; i < T; i++) {
        cin >> N;
        int result = 0;
        for (int i = 1; i <= N; i++)
            result += solve(N, i);
 
        cout << N - result << endl;
    }
    return 0;
}