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

문제 링크

 

이는 dp로 풀 수 있다.

dp(i,j) = i개의 디스플레이로 만들어졌으면서, m으로 나눈 나머지를 j인 수 중 최대인 수

라고 정의하면 

dp(i, (10*j+k)%m) = max(10*dp(i-1,j)+k) (0<=k<10)

dp(i, (100*j+11)%m) = max(100*dp(i-1,j)+11)

 

라고 식을 세울 수 있다.

 

n이 최대 9이므로 답의 최댓값은 10^18쯤 되므로 long long 자료구조형으로 dp테이블을 채워주면 된다.

 

코드