[C++] 백준 BOJ 6359 만취한 상범

문제링크 : https://boj.kr/6359

DP 문제라고 한다.

왜 DP 문제인지는 잘 모르겠지만 DP로 풀지 않으면 정말 쉽게 풀린다.

N이 5라고 가정하고 시뮬레이션을 해보자.

0은 문이 닫힌 상태를 1은 문이 열린 상태를 의미한다.

맨 처음

0 0 0 0 0

1라운드

1 1 1 1 1

2라운드

1 0 1 0 1

3라운드

1 0 0 0 1

4라운드

1 0 0 1 1

5라운드

1 0 0 1 0

이쯤 하면 규칙을 찾을 수 있다.

각 라운드에 해당하는 숫자만큼의 배수를 찾아서 1 → 0 / 0 → 1 으로 바꿔주면 된다.

// BOJ 6359 만취한 상범
#include <iostream>
#include <vector>
 
using namespace std;
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    int tc, num;
    cin >> tc;
    while (tc--) {
        cin >> num;
        vector<bool> prison(num + 1, false);
        for(int i = 1; i <= num; i++)
            for(int j = i; j <= num; j += i)
                prison[j] = !prison[j];
 
        int result = 0;
        for(int i = 1; i <= num; i++)
            result += prison[i];
        cout << result << '\n';
    }
 
    return 0;
}

N = 100 까지를 미리 구하면 DP? 라고 할 수도 있겠다.

// BOJ 6359 만취한 상범
#include <iostream>
 
using namespace std;
 
bool prison[101];
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int tc, num;
    cin >> tc;
    
    for(int i = 1; i <= 100; i++)
        for(int j = i; j <= 100; j += i)
            prison[j] = !prison[j];
    
    while (tc--) {
        cin >> num;
        int result = 0;
        for(int i = 1; i <= num; i++)
            result += prison[i];
        cout << result << '\n';
    }
    return 0;
}

하지만, 뭔가 아쉽다. N을 10으로 해서 다른 단순한 규칙이 없나 찾아보자.

0 - 0 0 0 0 0 0 0 0 0 0

1 - 1 1 1 1 1 1 1 1 1 1

2 - 1 0 1 0 1 0 1 0 1 0

3 - 1 0 0 0 1 1 1 0 0 0

4 - 1 0 0 1 1 1 1 1 0 0 

5 - 1 0 0 1 0 1 1 1 0 1

6 - 1 0 0 1 0 0 1 1 0 1

7 - 1 0 0 1  0 0 0 1 0 1

8 - 1 0 0 1 0 0 0 0 0 1

9 - 1 0 0 1 0 0 0 0 1 1

10- 1 0 0 1 0 0 0 0 1 0

만취한 상범이의 미친 짓을 수행할 때 마다 문이 열리고 닫히는 것은 계속 수행하다보면

전 라운드의 값을 메모이제이션 할 수 있는 것을 알 수 있다.

이를 토대로 DP로 풀면 된다.

하지만, 또 다른 규칙을 발견할 수 있는데..

N라운드 시행 이후 문이 열려있는 감옥은 우연히도 제곱수인 것을 확인할 수 있다...!

0 - 1 2 3 4 5 6 7 8 9 10

0 - 0 0 0 0 0 0 0 0 0 0

1 - 1 1 1 1 1 1 1 1 1 1

2 - 1 0 1 0 1 0 1 0 1 0

3 - 1 0 0 0 1 1 1 0 0 0

4 - 1 0 0 1 1 1 1 1 0 0 

5 - 1 0 0 1  0 1 1 1 0 1

6 - 1 0 0 1 0 0 1 1 0 1

7 - 1 0 0 1  0 0 0 1 0 1

8 - 1 0 0 1 0 0 0 0 0 1

9 - 1 0 0 1 0 0 0 0 1 1

10- 1 0 0 1 0 0 0 0 1 0

결론은.. N보다 작은 제곱수가 몇개인지만 구하면 된다.

N을 루트 씌우고 소수점을 떼면... 답이 나온다.

DP로 풀어도 되지만 DP로 푸는 것보다 훨씬 간단하다.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19

// BOJ 6359 만취한 상범 #include <iostream> #include <cmath> using namespace std;   int main() {     ios_base::sync_with_stdio(false);     cin.tie(NULL);     cout.tie(NULL);       int tc, num;     cin >> tc;     while (tc--) {         cin >> num;         cout << int(sqrt(num)) << '\n';     }       return 0; } Colored by Color Scripter

cs