7-세그먼트 디스플레이( BOJ 18118 )

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

18118번: 7-세그먼트 디스플레이

 

문제 파악하기

N개의 디스플레이에 숫자를 표시하여 만들 수 있는 가장 큰 M의 배수를 구하는 문제입니다. 주의할 점은 디스플레이에는 0부터 9까지 숫자와 11을 넣을 수 있다는 점입니다. 만들 수 있는 숫자는 대략 가늠해봐도 1억개 그 이상이라 단순히 반복문을 사용해서는 찾을 수 없습니다. 그렇다면 어떤 방법이 있을까요? 이런 경우, 효율적인 탐색 방법이 필요하며 그 때 생각할 수 있는 접근 방식은 총 2가지입니다.

 

문제 해결하기

우선, 가장 보편적으로 떠올리는 방법은 가장 큰 배수를 찾는 공식이나 방법을 떠올려보는 것입니다. 전문 용어로 그리디 방식이라고 표현하는데, 이 방식은 답을 도출하는데 명확한 증명이 없다면 무용지물인 방식입니다. 아쉽게도 이 문제에서 그리디를 사용하는 방식은 그리 쉬워보이지 않을 뿐더러 증명하기에도 어려울 듯 합니다. 그렇다면 다른 방법을 떠올려봅시다.

 

많은 사람들은 보통 효율적인 탐색, 중복 없는 탐색을 말할 때에는 보통 동적 프로그래밍을 떠올리곤 합니다. 하지만 동적 프로그래밍 기법을 사용하기 위해서는 선행될 조건이 있는데, 바로 관계를 찾아야 합니다. 보통 이 과정을 점화식을 설계한다고 표현하는데 이 문제는 다행히  동적 프로그래밍을 사용할 수 있는 방법이 있습니다. 2차원 배열 DP를 다음과 같이 정의해봅시다.

DP[ idx ][ mod ] = idx번째 디스플레이를 사용하여 만든 숫자 중 mod값의 나머지를 가진 숫자 중 가장 큰 숫자

 

DP를 다음과 같이 설계하면 우리는 배열 값 사이의 관계를 도출할 수 있습니다. 하나의 디스플레이에는 0~9, 그리고 11만이 들어갈 수 있습니다. 그렇다는 건, 현재 DP[idx][mod]에 있는 값에서 맨 뒤에 숫자들을 붙이고 그 때의 나머지를 구하면 우리는 DP[idx+1]열의 값을 구할 수 있습니다. 이렇게 다음 상태를 찾아서 해당 배열에 만들 수 있는 가장 큰 숫자를 계속 탐색하면 우리가 원하는 결괏값을 구할 수 있습니다.

 

소스코드

#include <stdio.h>
#include <string.h>
#include <algorithm>
#define NMAX 10
#define MMAX 100010
using namespace std;
 
int T, N, M;
 
long long int dp[NMAX][MMAX];
 
int main() {
    scanf("%d", &T);
    while(T--) {
        // input
        scanf("%d %d", &N, &M);
 
        // init
        memset(dp, 0, sizeof(dp));
        for(int j=0;j<=11;j++) {
            if(j==10) continue;
            dp[1][j%M] = j;
        }
 
        // dp
        for(int i=1;i<N;i++) {
            for(int j=0;j<M;j++) {
                if(!dp[i][j]) continue;
 
                for(int k=0;k<10;k++) dp[i+1][(j*10+k)%M] = max( dp[i+1][(j*10+k)%M], dp[i][j]*10+k );
                dp[i+1][(j*100+11)%M] = max( dp[i+1][(j*100+11)%M], dp[i][j]*100+11 );
            }
        }
 
        // print
        printf("%lld\n", dp[N][0]);
    }
}

 

후기

처음 문제를 보았을 때에는 접근 방법이 어려울 듯 하지만 막상 고민하면 쉽게 풀렸던 문제입니다. 다만, 시작 설정이 까다로웠던 점이 기억에 남습니다. 다이나믹 프로그래밍을 연습하기 좋은 문제라고 생각합니다.