[백준] No.3687 - 성냥개비 (C++, DP)
문제
https://www.acmicpc.net/problem/3687
3687번: 성냥개비
각 테스트 케이스에 대해서 입력으로 주어진 성냥개비를 모두 사용해서 만들 수 있는 가장 작은 수와 가장 큰 수를 출력한다. 두 숫자는 모두 양수이어야 하고, 숫자는 0으로 시작할 수 없다.
www.acmicpc.net
풀이
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 임을 주의하자.
코드