[BOJ] 3687 - 성냥개비

BOJ 3687 - 성냥개비 https://www.acmicpc.net/problem/3687

새로운 문제를 풀어보고 싶어서 찾아보다가 발견한 문제.

단순 규칙을 찾는 문제와, DP로 풀어야 하는 문제가 섞여있어서 재밌었다.

처음 문제를 읽었을 때는 당황할 수 있으나, 종이에 성냥개비를 그려보며 차근차근 생각해보면 쉽게 풀 수 있는 문제다.

성냥개비에 대해 생각해보기

문제에서 그림으로 보여준 성냥개비로 표현한 십진수를 뜯어보면 아래와 같은 사실을 얻을 수 있다.

• 각 숫자를 표현할 때 사용한 성냥개비의 개수는 상이하다.
  • 숫자 한개를 표현하는데 사용하는 성냥개비의 개수는 2~7개 사이다.
  • 2개 : 1, 3개 : 7, 4개 : 4, 5개 : 2,3,5, 6개 : 6,9,0, 7개 : 8
• 성냥개비를 가장 적게 사용해서 표현하는 숫자와, 가장 많이 사용해서 표현하는 숫자는 각각 1개다.
  • 가장 적게 사용해서 표현하는 숫자 : 1 (2개 사용)
  • 가장 많이 사용해서 표현하는 숫자 : 8 (7개 사용)

가장 큰 숫자 만들기

이 쯤에서, 아래와 같은 생각을 할 수 있게 된다.

주어진 성냥개비로 가장 큰 수를 만드려면, 성냥개비를 가장 적게 사용해서 표현할 수 있는 숫자를 열심히 만들어서 길게 늘어놓는다.

예를 들어 24개의 성냥개비가 주어졌다고 해보자.

숫자 9의 경우 성냥개비 6개를 사용해서 만들 수 있는데, 24개를 사용해서 늘어놓는다면 9999가 될 것이다.
그렇다면 9999가 가장 큰 숫자일까?

위에서 언급했듯이 숫자 1의 경우 성냥개비 2개를 사용해서 만들 수 있다. 24개를 사용해서 늘어놓는다면 111111111111이 될 것이다.

성냥개비 1개만 사용해서 만들 수 있는 숫자는 없으므로, 만약 주어진 성냥개비가 홀수개인 경우에는 맨앞에 성냥개비 3개로 만들 수 있는 숫자를 만들어서 늘어놓으면 된다.

성냥개비 3개로 만들 수 있는 숫자는 7 한개만 존재하기 때문에 정답은 7111111.... 형태가 된다.

정리해보자면 아래와 같다.

• 성냥개비 짝수개로 만들 수 있는 가장 큰 숫자 : 1111111.....
• 성냥개비 홀수개로 만들 수 있는 가장 큰 숫자 : 7111111..... (3개인 경우는 7)

이렇게 가장 큰 숫자를 구할 수 있었다.

가장 작은 숫자 만들기

가장 작은 숫자를 만드는 것은 큰 숫자 만들기보다는 좀 더 어렵다.

우선, 성냥개비 2개부터 10개까지의 정답을 손으로 구해보자.

2개 : 1
3개 : 7
4개 : 4
5개 : 2
-> 2,3,5중 가장 작은 숫자가 2
6개 : 6
-> 숫자는 0으로 시작할 수 없다는 문제 조건에 따라, 0이 될 수 없다.
   따라서 6,9중 가장 작은 숫자인 6이 정답
7개 : 8
8개 : 10
-> 7개를 넘기 때문에 한자리 숫자는 만들 수 없고, 꼭 두자리 숫자 이상이여야함.
   2개로 1을 만들 수 있고, 나머지 6개로 0을 만들 수 있으므로 정답은 10
9개 : 18
-> 2개로 1을 만들 수 있고, 나머지 7개로 8을 만들 수 있음
10개 : 22
-> 2개로 1을 만들면 8개가 남기 때문에 더이상 십의 자리에 1이 들어올 수 없음.
   5개로 2를 만들면 십의 자리를 가장 작게 만들 수 있고, 남은 5개로 2를 만들 수 있으므로 정답은 22

이후 몇개를 더 나열해보면 아래와 같은 사실을 알 수 있다.

• 전혀 사용할일이 없는 숫자가 존재한다.
  • 가장 작은 숫자를 만들어야 하므로 굳이 성냥개비 5개로 3, 5를 만들거나 성냥개비 6개로 9를 만들 필요가 없다.
• 6개를 사용해서 숫자를 만들 때 예외가 존재한다.
  • 0으로 시작할 수 없다 == 한자리인 경우에도 0은 허용되지 않는다
  • 단, 첫 자리만 아니면 그 뒤에는 0이 올 수 있다.
  • 정답이 한자리 숫자거나, 두자리를 넘으면서 가장 첫번째 자리를 성냥개비 6개로 만들어야 할 때 : 6
  • 정답이 두자리를 넘으면서, 첫번째 자리가 아닌 곳을 성냥개비 6개로 만들어야 할 때 : 0
• 숫자가 아무리 길어져도, a개로 만들 수 있는 최소 숫자 + b개로 만들 수 있는 최소 숫자 + c개로 만들 수 있는 최소 숫자 + ...의 규칙을 벗어날 수 없다.
  • 단, 6개를 사용해서 숫자를 만들 때의 예외는 있다. (윗 내용 참고)

2~7개로 만들 수 있는 최소 숫자를 나열해보면 [1, 7, 4, 2, 0, 8] 이다. 이 배열을 min이라고 하고, 정답이 들어가는 배열을 DP라고 하자.

(아래 나오는 +는 사칙연산의 더하기가 아니고, 앞 숫자에 뒤 숫자를 붙인다는 의미로 사용하였다)

• 8개로 만들 수 있는 최소 숫자인 10은 결국 2개로 만들 수 있는 최소 숫자인 1과 6개로 만들 수 있는 최소 숫자인 0의 조합이라고 볼 수 있다.
  • 이 것을 다르게 표현하자면 DP[8] = min[2] + min[6]
• 9개로 만들 수 있는 최소 숫자인 18은 결국 2개로 만들 수 있는 최소 숫자인 1과 7개로 만들 수 있는 최소 숫자인 8의 조합이라고 볼 수 있다.
  • DP[9] = min[2] + min[7]
• 10개로 만들 수 있는 최소 숫자인 22은 결국 5개로 만들 수 있는 최소 숫자인 2를 연속으로 조합한 것이라고 볼 수 있다.
  • DP[10] = min[5] + min[5]
  • 4개 + 6개, 3개 + 7개 등의 조합도 있지만 어떤 것을 조합해보아도 22보다 작게 만들 수 없다는 것을 알 수 있다.
• 15개로 만들 수 있는 최소 숫자는 108인데, 결국 2개로 만들 수 있는 최소 숫자인 2와 6개로 만들 수 있는 최소 숫자인 0, 그리고 7개로 만들 수 있는 최소 숫자인 8을 조합한 것이다.
  • 다르게 표현하면 8개로 만들 수 있는 최소 숫자인 10에 7개로 만들 수 있는 최소 숫자인 8을 붙인 것이다.
  • DP[15] = (min[2] + min[6] + min[7]) = (min[8] + min[7])
  • 2개 + 7개 + 8개라던가 5개 + 5개 + 5개 등의 조합도 있지만 어떤 것을 조합해보아도 108보다 작게 만들 수 없다.

이런 식으로 세자리, 네자리 숫자를 만들어 나가다보면 아래와 같은 식을 세울 수 있다.

DP[n] = (DP[n-2] + min[2], DP[n-3] + min[3], ..., DP[n-7] + min[7]) 중 가장 작은 값

코드

나같은 경우는 최소값을 저장할 배열을 min으로, 맨 뒤에 붙이는데 사용할 배열을 add라고 만든 뒤에 min[2] ~ min[8]을 미리 채워넣었다.
그리고 min[9]부터 구하도록 코드를 짰더니 Java 기준 80ms로 통과!

전체 코드