천상용섬( BOJ 12758 )

문제 : https://www.acmicpc.net/problem/12758

12758번: 천상용섬

 

문제 파악하기

제시된 N개의 약수를 오름차순으로 나열하는 경우의 수를 구하는 문제입니다. N의 개수는 300개라서 많지 않지만 입력되는 숫자가 최대 1,000,000이기 때문에 단순히 모든 숫자를 비교하기에는 너무 오랜 시간이 필요합니다. 그렇기에 우선, 빠르게 구할 수 있는 값부터 먼저 구해봅시다. 어떤 수(K)의 약수를 구하기 위해서는 1부터 K까지의 수를 모두 비교할수도 있지만, 1부터 √K까지만 확인해도 충분히 구할 수 있습니다. 이렇게 약수를 빠르게 구하면 나머지는 적절하게 재귀함수를 설계해서 문제를 풀 수 있습니다.

 

문제 해결하기

모든 수의 약수를 빠르게 구했다면 이제는 문제를 해결하기 위해 필요한 배열을 설계할 시간입니다. 제시된 N개의 수를 순서대로 확인하기 위해서는 현재 숫자의 위치를 나타내는 변수인 idx가 필요하며, 이전에 사용했던 약수를 표현할 변수 bef가 있습니다. 우리는 앞에서 제시한 변수 2개를 사용하여 배열을 다음과 같이 정의할 수 있습니다.

dp[idx][val] : 현재 idx번째 숫자의 약수 중 val 이상의 숫자를 사용해서 나열할 수 있는 경우의 수

 

이렇게 탐색에 필요한 배열을 선언한 다음에는 재귀함수를 이용하여 문제를 해결할 수 있습니다. 여기서 중요한 점은 val을 숫자 그대로 사용해서는 안 된다는 점입니다. 대신, val을 이전에 사용한 숫자의 번호로 지정해야 합니다. val을 숫자 그대로 사용한다면 배열의 크기가 너무 커지기 때문에 효율적인 탐색이 힘들어집니다. 대신, 우리는 약수를 모두 구한 다음에 이분 탐색을 활용하여 이전 숫자보다 크거나 같은 숫자를 찾아서 탐색을 하면 훨씬 효율적인 탐색을 할 수 있습니다.

 

소스코드

#include <iostream>
#include <string.h>
#include <vector>
#include <algorithm>
#define NMAX 305
#define VMAX 250
#define MOD 1000000007
using namespace std;
typedef long long int lint;
 
int T, N, t;
vector< int > inp[NMAX];
 
int pos;
lint dp[NMAX][VMAX];
 
int bsearch(int idx, int val) {
    int l, r, mid;
    
    l = 0; r = (int)inp[idx].size()-1;
    while(l<=r) {
        mid = (l+r)/2;
        
        if(inp[idx][mid] < val) l = mid+1;
        else r = mid-1;
    }
    
    return l;
}
 
lint sv(int idx, int bef) {
    if(dp[idx][bef] >= 0) return dp[idx][bef];
    
    if(idx > N) return dp[idx][bef] = 1;
    else {
        lint ret = 0;
        
        if(idx == 0) pos = 0;
        else pos = bsearch(idx, inp[idx-1][bef]);
        
        for(int k=pos;k<inp[idx].size();k++) ret = (ret + sv(idx+1, k))%MOD;
        
        return dp[idx][bef] = ret;
    }
}
 
int main() {
    cin >> T;
    while(T--) {
        // init
        for(int i=0;i<NMAX;i++) inp[i].clear();
        memset(dp, -1, sizeof(dp));
        
        // input
        cin >> N;
        for(int i=1;i<=N;i++) {
            cin >> t;
            
            for(int j=1;j*j<=t;j++) {
                if(t%j == 0) {
                    inp[i].push_back(j);
                    if(j != t/j) inp[i].push_back(t/j);
                }
            }
            
            sort(inp[i].begin(), inp[i].end());
        }
        
        // solve
        inp[0].push_back(0);
        printf("%lld\n", sv(0, 0));
    }
}
 

후기

약수와 동적 프로그래밍을 합친 문제입니다. 처음 보는 유형이라 재미있게 문제를 풀었네요. 기본적인 약수 판별과 이분 탐색, 그리고 동적 프로그래밍을 한번에 연습할 수 있기에 기초적인 알고리즘을 습득한 사람에게 추천하고 싶은 문제입니다.