백준 6359 만취한 상범

// 30분
// d[i] = 방의 갯수가 i개 일 때 열려있는 방의 갯수.
#include <cstdio>
using namespace std;
 
int a[101]; // i번째 약수의 갯수
int d[101];
 
int main() {
    int t;
    scanf("%d", &t);
    for (int i = 1; i <= 100; i++) {
        for (int j = 1; j * j <= i; j++) {
            if (i%j == 0) a[i] += 2;
            if (j*j == i) a[i] -= 1;
        }
    }
    for (int i = 1; i <= 100; i++)
        d[i] = d[i - 1] + (a[i] % 2 == 0 ? 0 : 1);
    while (t--) {
        int n;
        scanf("%d", &n);
        printf("%d\n", d[n]);
    }
    return 0;
}
 

DP 문제

먼저 1~100까지 각각의 약수의 갯수를 구해준뒤 문제를 해결하였다.

약수의 갯수를 구하는 시간을 줄이기 위해 제곱수를 이용하였다.

약수의 성질을 이용하면 약수란 나누었을 때 0이 되게 하는 수 이므로

14번 줄  if (i%j == 0) a[i] += 2;

즉, i의 약수는 나누었을 때 0이 되는 j 이다. 그리고 약수의 성질을 잘 살펴보면

제곱수를 제외하고는 항상 짝을 이룬다.

예를 들어

10의 약수는 1, 2, 5, 10 인데 1은 10과 짝을 이루고 2는 5와 짝을 이루므로 

10과 같이 제곱수가 아닌 경우에는 sqrt(10)까지만 연산을 하되 2씩 더해주면 된다.

====================================

여기서 제곱수는 예외가 되는데 

1에서 10까지 약수의 갯수를 나열해 보면 다음과 같다.

1 2 3 4 5 6 7 8 9 10

1 2 2 3 2 4 2 4 3  4

제곱수에 해당하는 1,4,9 만 약수의 갯수가 홀수 인 것을 알 수 있다.

그러므로 제곱수에 해당하는 수의 약수를 구한 뒤에는 다음과 같이 1을 빼준다.

15번 줄  if (j*j == i) a[i] -= 1;

각각의 약수의 갯수를 구한 이후 dp의 성질을 이용하면 다음과 같다.

19번 줄  d[i] = d[i - 1] + (a[i] % 2 == 0 ? 0 : 1);

d[i] = i-1번째 까지 열린방의 갯수 + 현재 방의 상태

※ 정리해보면, 1~10까지 직접 나열하여 방이 열려있는 유무를 확인해보면

최종적으로 "약수의 갯수"가 짝수일 때 닫혀있고, 홀수일 때 열려있다는 것을 알수 있다.

그리고 약수의 갯수가 짝수라는 것은 해당 수가 제곱수라는 뜻이다.

<DP를 이용한 일반적인 풀이법>

// 30분
// d[i] = 방의 갯수가 i개 일 때 열려있는 방의 갯수.
#include <cstdio>
using namespace std;
 
int main() {
    int t;
    scanf("%d", &t);
    while (t--) {
        int n;
        scanf("%d", &n);
        int d[101] = { 0 }; // 모든 원소를 0으로 초기화 시킴.
        for (int i = 1; i <= n; i++) {
            for (int j = 1; i * j <= n; j++) {
                if (d[i*j]) d[i*j] = !d[i*j];
                else d[i*j] = !d[i*j];
            }
        }
        int sum = 0;
        for (int i = 1; i <= n; i++) sum += d[i];
        printf("%d\n", sum);
    }
    return 0;
}