[백준/BOJ] 1416 팬 서비스★ - 접근과 풀이(C++)

예전에 풀었던 문제중 기억나는 dp문제가 있어서 다시 풀어보았다. 공부하기 싫을땐 알고리즘이 최고.

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

분류 : dp

접근 방법

티켓번호가 2K자리이고, 1번조건과 2번조건중 하나 이상을 만족해야한다.

이전에 플레2짜리 dp문제를 푼 적이 있는데, 비슷한 접근을 사용했다.

1번조건 + 2번조건 - (1번 && 2번) 을 기본 틀로 사용하였다.

​

머리를 조금 써보면, 1번조건과 2번조건은 구하는 방법이 똑같다. K자리의 숫자를 나열하는 방법의 가짓수의 제곱이다. 사실 티켓의 첫번째 자리에 0이 들어올수 있었기에 가능한거고, 만약 0이 안되었더라면 문제가 더 복잡해졌을것 같다.

​

K자리의 숫자를 n개의 수로 만든다고 할 때, $n^K$, 최대 10^50의 가짓수가 나온다. 나열하는 방법보다 나열한 숫자의 합과 방법의 가짓수 중요하므로, 배열에 가짓수를 저장하는 방법을 사용하였다.

sum[101][10000] 배열을 사용하였고, sum[i][j]는 i자리까지 숫자를 사용했을 때 합이 j인 방법의 가짓수이다. 사실 i는 50, j는 450이 최대이므로 배열을 크게 안잡아도 된다.

핵심은 1번조건과 2번조건을 모두 만족하는 경우의 수를 찾는 것이다.

설명을 돕기위해 그림을 가져왔다. 1번조건과 2번조건을 수식으로 적으면

1번조건 : a+c=b+d

2번조건 : a+b=c+d 이고, 항등식 이므로1번 식에서 2번 식을 빼면

b=c, a=d라는 중요한 조건이 나온다.

그래서 앞선 1,2번 조건을 계산한 방법과 비슷하게

b = c를 만드는 경우의 수 * a = d를 만드는 경우의 수가 된다.

그리고 모듈러연산 항상 조심할 것.

풀이

#include<iostream>
#include<string.h>
#include<vector>
#define MOD 999983
using namespace std;
int K;
string str;
vector<long long> vnum;
long long sum[101][10000]={0};  //sum[i][j]는 총 i개의 숫자의 합이 j인 개수
long long calc1(){
    long long ret=0;
    for(int i=0;i<10000;i++){
        if(sum[K][i]>0)
            ret+=sum[K][i]*sum[K][i];
        ret%=MOD;
    }
    return ret;
}
long long calc3(){
    long long ret1=0,ret2=0;
    for(int i=0;i<10000;i++){
        if(sum[(K+1)/2][i]>0)
            ret1+=sum[(K+1)/2][i]*sum[(K+1)/2][i];
        ret1%=MOD;
    }
    for(int i=0;i<10000;i++){
        if(sum[K/2][i]>0)
            ret2+=sum[K/2][i]*sum[K/2][i];
        ret2%=MOD;
    }
    return (ret1*ret2)%MOD;
}
int main(){
    cin>>K;
    cin>>str;
    if(K==1){
        cout<<str.length();
        return 0;
    }
    for(int i=0;i<str.length();i++){
        vnum.push_back(str[i]-'0');
        sum[1][str[i]-'0']=1;
    }
    for(int i=2;i<=K;i++){ //k자리 가능한 합의 개수
        for(int j=0;j<10000;j++){
            for(int k=0;k<vnum.size();k++){
                if(sum[i-1][j]>0)
                    sum[i][j+vnum[k]]+=sum[i-1][j];
                sum[i][j]%=MOD;
            }
        }
    }
        cout<<(calc1()*2+MOD-calc3())%MOD;
}