백준 6359 만취한 상범(dynamic programming)

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

6359번: 만취한 상범

#include <iostream>
#include <cstring>

using namespace std;
int N;
int cache[101];
int sum;
void people(int num)
{
    for (int i = 1; i <= num; i++)
    {
        for (int j = 1; i * j <= num; j++)
        {
            cache[i * j] = !cache[i * j];
        }
    }
    for (int i = 1; i <= num; i++)
        sum += cache[i];
    cout << sum;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> N;
    while (N--)
    {
        int num;
        cin >> num;
        people(num);
        cout << "\n";
        memset(cache, 0, sizeof(cache));
        sum = 0;
    }
}

그렇게 어려운 문제는 아니었지만 짚고 넘어가야할 것들이 몇 개 있어서 블로그에 올린다.

 

N 이하의 제곱수만 세는 간단한 방법이 있긴 하지만, dp 문제이기 때문에 dp스럽게 저렇게 푼다. 각 단계마다 그 단계의 배수들이 toggle 되게 만들면 된다.

 

여기서 짚고 넘어가야할 두가지!!!!!

 

• testcase가 1개 초과인 경우!!! 모든 값들을 초기화 시키고 다음 testcase로 넘어가게 만들어야 한다. 종만북 풀 때 거기 문제들은 항상 testcase가 1초과여서 익숙하게 했었는데 벌써 까먹었다.
• cache 배열이 int형이지만 마치 bool type인 것 처럼 사용이 가능하다.( !cache[i][j]로 cache[i][j]를 toggle 시킴) 기억하고 있으면 또 언젠가 요기나게 쓸 날이 올 것이다.