1086. 박성원

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

1086번: 박성원

 

 

티어 : 플래5

 

정말 오랜만에 DP문제를 풀어봤다. 꽤 난이도가 있었는데, 적용되는 dp 개념자체는 어렵지 않고, 메모이제이션 해주는 방법이랑 구현 과정이 난이도가 있어 티어가 플래티넘인 것 같다.

 

메모이제이션 구현 방법이 잘 생각나지 않아 계속 고민하고 있었는데,

비트 방식으로 메모이제이션을 구현하는 아이디어를 얻어 해결할 수 있었다.

 

문제를 해결할 로직을 구체적으로 정리한 후 본격적으로 코딩을 시작하기 전에 다른 사람의 블로그 글을 참고하였는데, 이 때 "비트 방식" 4글자를 보자마자 이마를 탁 치며 코딩을 시작하였다. 좀 더 고민해서 내 스스로 이런 아이디어를 생각해냈으면 어땠을까 하는 아쉬움과 후회도 남는다.

 

백준 풀기 시작한지 얼마 안됐는데도, 요새 코드를 한 번에 완성하는 실력이 꽤 늘은게 느껴진다.

로직을 구상하고 코드를 한번에 뽑아냈을 때, 그 완성도가 점차 느는 것 같다. 수정하는 시간과 양이 줄어드는게 체감된다.

 

이번 여름 방학 기간동안 플래티넘 이상 티어의 문제들을 더 많이 도전해봐야겠다.

 

#include<stdio.h>
#include<string.h>
#include<stdlib.h>

char s[20][55];
struct str{
    int l;
    int r;
} arr[20];

long long int dp[32770][105], dpCH[32770];
int n, k, tot_len;

int remain(int x, int i){
    for( ; i>0 ; i--){
        x *= 10;
        x %= k;
    }
    return x;
}

int mul2(int x){
    int re = 1;
    for(int i=0 ; i<x ; i++) re *= 2;
    return re;
}

long long int f(int index, int re, int len){
    if(dpCH[index] == 1) return dp[index][re];
    
    int bit = index;
    for(int i=0 ; i<n ; i++){
        if(bit % 2 == 1){
            int rem = remain(arr[i].r, len-arr[i].l);
            f(index - mul2(i), (re - rem + k) % k, len-arr[i].l);
            for(int j=0 ; j<k ; j++){
                dp[index][ (j + rem) % k ] += dp[index - mul2(i)][j];
            }
        }
        bit /= 2;
    }
    dpCH[index] = 1;
    return dp[index][re];
}

long long int nfct(int n){
    long long int re = 1;
    for(int i=1 ; i<=n ; i++) re *= i;
    return re;
}

long long int gcd(long long int x, long long int y){
    if(x == 0) return y;
    return gcd(y%x, x);
}

int main()
{
    scanf("%d", &n);
    for(int i=0 ; i<n ; i++) scanf("%s", s[i]);
    scanf("%d", &k);

    for(int i=0 ; i<n ; i++){
        arr[i].l = strlen(s[i]);
        tot_len += arr[i].l;
        for(int j=arr[i].l-1 ; j>=0 ; j--){
            arr[i].r += remain((s[i][j] - '0'), arr[i].l - j - 1);
        }
        arr[i].r %= k;
        dp[mul2(i)][arr[i].r] = 1;
        dpCH[mul2(i)] = 1;
    }

    int init = 0;
    for(int i=0 ; i<n ; i++) init += mul2(i);

    long long int output = f(init, 0, tot_len), g = gcd(f(init, 0, tot_len), nfct(n));
    printf("%lld/%lld", output/g, nfct(n)/g);
}