7-세그먼트 디스플레이 C++ - 백준 18118

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

재미있었던 DP 문제

문제 접근

태그를 까고 나서 바로 접근이 생각났다

$d(i,j,k)$를 $i$번째 세그먼트가 $j$이면서$\mod m$ 값이 $k$인

최대 자연수를 담는다고 하고 접근했다.

이후 각 세그먼트의 digit을 관리할 필요 없다는 것을 보고

$d(i,j)$ 로 바꿔서 생각했다.

나는 위처럼 $d(i-1,j)\rightarrow d(i,(j+t)\mod m)\;\;t=k\times 10^l$ 식으로 가는 형태로

숫자를 앞에 붙이는 방식으로 코딩했는데

이는 11의 존재 때문에 숫자를 앞에 붙일 때 번거로움이 있을 뿐더러

WA를 받았다.

반례 생각이 직관적으로 떠오르지 않지만 각 digit이

0일때 분명히 문제가 생길 것 같다.

따라서 0을 확실히 안고 갈 수 있게 뒤에다가 숫자를 붙여서 코드를 짜야했다.

(실제 정해도 숫자를 뒤에 붙인다.)

정리

$d(i-1,j)\rightarrow d(i,(t+k)\mod m)\;\;t=d(i-1,j)\times10^l,(l=1,2)$

뒤에 11을 붙이는 경우는 원래 숫자에 100곱하고 더하고 0~9 붙이는 경우는

10만 곱하여 처리하면 된다.

코드는 다음과 같다.

#include <bits/stdc++.h>
typedef long long ll;
using namespace std;

ll dp[10][100000];

int main(){
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    int t;
    cin >> t;
    while(t--){
        int n,m;
        cin >> n >> m;
        fill(dp[0],dp[10],-1);
        for(int i=0;i<10;i++) dp[0][i%m]=i;
        dp[0][11%m]=11;
        for(int i=1;i<n;i++){
            for(int j=0;j<m;j++){
                if(dp[i-1][j]==-1) continue;
                for(int k=0;k<10;k++){
                    ll add=dp[i-1][j]*10+k;
                    dp[i][add%m]=max(dp[i][add%m],add);
                }
                ll add=dp[i-1][j]*100+11;
                dp[i][add%m]=max(dp[i][add%m],add);
            }
        }
        cout << dp[n-1][0] << '\n';
    }
    return 0;
}