백준 6359번 : 만취한 상범 C++

BOJ 6359번 만취한 상범 문제

구현을 하다가 잘 안돼서 문제 분류를 보니 다이나믹 프로그래밍이였다.

다이나믹 프로그래밍으로 풀긴 했는데 생각을 해내는게 더 중요한 거 같다.

6359.cpp

#include <bits/stdc++.h>
using namespace std;
bool dp[101];
void solve() {
    memset(dp, 0, sizeof(dp));
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        for (int j = i; j <= n; j += i) {
            if (dp[j])
                dp[j] = false;
            else
                dp[j] = true;
        }
    }
    int count = 0;
    for (int i = 1; i <= n; i++) {
        if (dp[i]) count++;
    }
    cout << count << '\n';
}
int main() {
    int n;
    cin >> n;
    while (n--) {
        solve();
    }
}