[BOJ 26570 // C++] Semiperfect

※ 정확하지 않은 내용을 담고 있을 수 있다 ※

 

이번에 볼 문제는 백준 26570번 문제인 Semiperfect이다.
문제는 아래 링크를 확인하자.

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

 

100만 미만의 양의 정수 \(m\)이 주어질 때, \(m\)의 자기 자신을 제외한 약수 중 일부(전체도 가능)의 합으로 \(m\)을 만들 수 있는지를 판별하는 문제이다.

 

100만 미만의 정수 중 가장 많은 수는 240개의 약수를 가진다(720720 등). 따라서 \(m\)의 모든 약수를 활용하여 \(m\)을 생성할 수 있는지 판단하는 방식으로 문제를 충분히 해결할 수 있다.

 

이러한 유형의 문제를 해결하는 대표적인 방법으로 knapsack dp가 있다. 특히 이 문제에서는 존재의 여부만을 확인하면 되므로 0과 1로 모든 상태를 표현할 수 있고, 따라서 비트셋을 활용한 knapsack 구현이 가능하다. 글쓴이는 이를 활용하여 문제를 해결하였다.

 

아래는 제출한 소스코드이다.

#include <iostream>
#include <bitset>
using namespace std;

int T;
bitset<1000000> st;

bool func(int n) {
    st = 0;
    st[0] = 1;
    for (int i = 1; i * i <= n; i++) {
        if (n % i) continue;
        if (i != n) st = (st << i) | st;
        if (n / i != n && n / i != i) st = (st << (n / i)) | st;
    }
    return st[n];
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> T;
    while (T--) {
        int x; cin >> x;
        if (func(x)) cout << "Semiperfect\n";
        else cout << "NOT Semiperfect\n";
    }
}