AtCoder : ABC 178 C - Ubiquity

atcoder.jp/contests/abc178/tasks/abc178_c

C - Ubiquity

DP문제이다. 점화식을 파악할 수 있다면 쉽고 간단한 문제겠지만, 그게 떠오르지 않는다면 역시 어렵다...

이러한 문제에 대해 어떻게 접근해야 할까? 이전 포스팅들에서 꾸준히 얘기하고 있지만,

 

필자가 이해하는 동적계획법(DP) 적용의 근거는 어떠한 정점(상황)에서 일정한 규칙을 적용하여 일정한 간격만큼 떨어진 다음 정점으로 넘어갈 때에 있다.

 

어떠한 정점에서 연결된 정점이 한 개뿐인데, 다음 정점에서는 다수의 이웃 정점들이 연결되어 있거나...

각 정점마다 규칙성 없는 처리/연산이 이루어진다면...

이렇게 각 정점의 연결관계, 연산방식이 모두 랜덤 하다면 이는 그래프 문제가 된다. 

하지만 항상 정점에서 일정한 규칙이 적용된다면, 동적계획법을 의심해 볼 수 있게 된다. 물론 그래프가 더 포괄적이어서 그래프를 적용해도 될 것이다. 하지만 연결되는 정점 수가 너무 많은 경우들이 있어서 이를 일일이 정의해주는 게 불가능한 경우가 많을 것이다. 

 

그렇다면 이 문제에서의 정점은 무엇일까?

정점은 숫자의 갯수(자릿수)이다. N은 몇 개의 숫자들이 사용되는지 입력으로 주어진다. 3이라면 첫 번째 숫자가 첫 번째 정점,..., 세 번째 숫자가 세 번째 정점이자 마지막 정점이 된다. 그리고 각 정점에서 이루어지는 일정한 연산/확인 필요 내용은 0이 들어있는지, 9가 들어있는지 아닌지이다. 그 내용이 어떤 상태 정보가 되어 저장되면 되는 것이다.

 

위의 그림과 같이, 어떠한 수가 있다면 그 수, 그리고 그 수까지 도달함에 있어서 4가지의 경우로 나눌 수 있게 된다.

 

위의 그림과 같이, 각 자리의 숫자가 정점이 되고 DP의 첫번째 '축'이 된다. 이제 4가지의 상태를 [2][2]로 나누어 각 DP[i]에 넣어주는 것이다. 위의 그림은 첫 번째 숫자에 대한 경우를 기록한 것이다. 0과 9가 한 수에 한꺼번에 등장할 수는 없으므로 DP[1][1][1]은 당연히 0이다. 

위의 그림은 이제 2개의 숫자가 있는 경우로 확장한 것이다.

0과 9 모두 포함되지 않은 경우는 8x8이다. 여기서 알 수 있는 것은 자릿 수가 증가할수록 이 위치의 경우의 수는 계속 '곱하기 8'이 이루어진다.

그리고 DP[i][0][1], 즉 0만 포함되는 경우는 이전에 0이 선택된 경우와 그렇지 않은 경우를 모두 고려해야 한다. 이전에 0이 선택되었다면 이번에 0부터 8까지 선택할 수 있다. 0을 또 선택해도 된다는 점에 유의한다. 그리고 이전에 0이 선택되지 않은 경우에는 이번에 반드시 0을 선택하면 된다. 그래서 8+1x9=17이 된다.

0,9가 모두 선택된 경우에도 한 가지 주의할 것이 있다. 두 개의 수만 있을 때는 단순히 1+1로 계산한 것 같지만, 저기에는 0x10이 숨어있다. 즉, 이전에 0,9가 모두 선택되었다면 이번에 어떤 수를 선택해도 된다는 점이다. 그래서 10을 곱해서 합산한다.

 

위의 그림에서 색깔이 같은 동그라미가 이전 DP값을 읽어서 이번 DP에 반영하는 부분이다. 이것이 바로 그림으로 표현된 점화식이다.

이와 같은 방법으로 N번 반복하여 답을 구할 수 있다. 나머지 연산에만 주의하자.

 

<주요 내용>

상태, DP, 동적계획법, 나머지 연산

 

<코드>

#include <iostream>
#define endl '\n'
using namespace std;
typedef long long ll;
const int sz=1e6+10,mod=1e9+7;
ll n,dp[sz][2][2];
// 행: 0이 없을 때, 있을 때
// 열: 9가 없을 때, 있을 때

int main()
{
    ios::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
    
    cin>>n;
    dp[1][0][0]=8;
    dp[1][0][1]=1;
    dp[1][1][0]=1;
    if(n==1){
        cout<<0<<endl;
        return 0;
    }
    for(int i=2;i<=n;++i){
        dp[i][0][0]=(dp[i-1][0][0]*8)%mod;
        dp[i][0][1]=(dp[i-1][0][0]+dp[i-1][0][1]*9)%mod;
        dp[i][1][0]=(dp[i-1][0][0]+dp[i-1][1][0]*9)%mod;
        dp[i][1][1]=(dp[i-1][0][1]+dp[i-1][1][0]+dp[i-1][1][1]*10)%mod;
    }
    cout<<dp[n][1][1]<<endl;
    return 0;
}