[백준] No.3687 - 성냥개비 (C++, DP)

문제

 

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

3687번: 성냥개비

 

풀이

 

solved.ac 난이도: Gold 2

 

가장 큰 수와 가장 작은 수를 만드는 방법을 나누어서 생각해보자.

 

1. 가장 큰 수 만들기 (그리디)

 

가장 큰 수를 만들기 위해서는 무엇보다 수의 자릿수를 늘리는 게 최선이다.

예를 들어 성냥개비로 만들 수 있는 가장 큰 한자리 수인 9를 만들기 위해서는 6개의 성냥개비를 써야 한다.

하지만 성냥개비 6개로 1을 3개 만들어 3자리 수 111을 만드는 것이 훨씬 큰 수를 만들 수 있다.

 

따라서 주어진 성냥이 짝수인 경우 성냥을 가장 조금 사용하는 '1'만을 이용하는 것이 가장 큰 수를 만들 수 있다.

홀수인 경우 1 다음으로 가장 적은 성냥으로 만들 수 있는 7(성냥 3개 소모)을 가장 앞자리 수로 사용하고 나머지 성냥으로는 모두 1을 만들어 준다.

 

결과적으로 n개의 성냥으로 만들 수 있는 최댓값은

짝수: 111....11(n/2개의 1)

홀수: 7111...11( 7 + (n-3)/2개의 1)

 

 

2. 가장 작은 수 만들기 (DP)

 

큰 수를 그리디로 만들 수 있어 작은 수도 그리디를 이용해 해결하려 할 수도 있는데, (제가 그랬습니다...)

성냥을 각 자릿수에 최대한 많이 써서 수를 만드는 것은 다음과 같은 케이스들에서 문제가 발생한다.

 

 

성냥이 10개인 경우

3개 + 7개 = 78

4개 + 6개 = 40

5개 + 5개 = 22

...

 

성냥이 11개인 경우

4개 + 7개 = 48

5개 + 6개 = 20

...

 

성냥이 17개인 경우

3개 + 7개 + 7개 = 788

...

5개 + 6개 + 6개 = 200

 

따라서 각 자리수에 성냥을 할당하는 모든 경우를 구해보아야 한다.

여기서 쓰고 남은 성냥이 n개일 때 미리 구해 놓은 최솟값을 재사용 가능하므로 메모이제이션을 활용하자.

 

dp[n]을 n개의 성냥으로 구성 가능한 최솟값이라고 하자.

이번 자릿수를 i(2~7)개의 성냥으로 구성하면 dp[n]은 다음과 같이 구할 수 있다.

dp[n] = min(dp[n], dp[n-i] + num[i])

 

여기서 num[i]는 i개의 성냥으로 만들 수 있는 가장 작은 한자리 수를 의미한다.

단, 0은 가장 앞자리 수가 될 수 없으므로 num[6] = 0 이지만 dp[6] = 6 임을 주의하자.

 

코드