[백준/Python] 3687번 성냥개비 풀이

문제 해석

---

문제 풀이

---

문제 알고리즘 선택

• 각 숫자별 필요한 성냥개비의 갯수는 아래와 같다
  

  1	2	3	4	5	6	7	8	9	0
  2	5	5	4	5	6	3	7	6	6

• 최대값
  • 2개(1)와 3개(7)이 최소 갯수이며 모든 성냥을 1과 7을 통해 소진 시킬 수 있으며 가장 많은 자리수를 가질 수 있도록 유도할 수 있다.
  • 따라서 최대값은 1과 7을 이용해 단순한 탐욕법 (그리디)로 풀어낼 수 있다.
• 최소값
  • 브루트 포스로 3,5,9와 같은 숫자를 제외한 모든 숫자로 만들어낸 성냥의 갯수를 이용하려고 했으나 최대값을 고려했을 때 시간 초과가 난다
  • 다시 한 번 17까지 모든 숫자를 계산해보았더니 이전 값에 새로운 자리수(0~9)를 추가하는 형태임을 발견했다.
    (그러나 6개일 때와 13개일 때와 같이 앞자리에 0이 올 수 없는 경우에 6으로 대체하는 부분이 필요)
  • 따라서 최소값은 dp (다이나믹프로그래밍)으로 풀어낼 수 있다.

풀이 과정

1. 최대값은 2로 나누어지는지 확인하고 나누어 떨어지면 모든 자리수를 1로 그렇지 않다면 7을 추가한 후 1을 추가
   
   
2. 최소값은 7개를 사용하는 경우까지 basis step으로 작성한 후 다음 숫자(N)부터는 0~9의 자연수를 추가한다고 할 때 기존에 있던 배열에 사용하는 성냥의 갯수 + 새로 추가될 자연수에서 필요한 성냥의 갯수 중 최소값을 가지도록 했다.
   ex: (10일 경우 0~9까지 자연수를 만드는데 드는 성냥은 최대 7개 최소 2개이므로 dp[10-i] + dp[i] (i: 2~7)이 된다

 

코   드

---

import sys
test_case = int(sys.stdin.readline())
minimum = [0,0,1,7,4,2,0,8,10] + [0] * 93

# for minimum range
for idx in range(9, 101):
    minimum[idx] = minimum[idx - 2] * 10 + minimum[2]
    for sub in range(3, 8):
        if idx - sub == 6:
            minimum[idx] = min(minimum[idx], 60 + minimum[sub])
        else:
            minimum[idx] = min(minimum[idx], minimum[idx - sub] * 10 + minimum[sub])
minimum[6] = 6
    
for _ in range(test_case):
    maximum = 0
    matches = int(sys.stdin.readline())

    print(minimum[matches], end=' ')
    
    if matches % 2 == 0:
        for i in range(matches//2):
            print('1', end='')
    else:
        print('7', end='')
        for i in range((matches - 3)//2):
            print('1',end='')
    print()

느낀점: 처음에 최대값을 잘못생각해서 브루트포스 실수를 하고 시간 초과가 났다. 실제 코딩 테스트 때 히든 케이스에 걸리지 않도록 잘 생각하고 패턴을 잘 찾아야겠다.

날짜: 2024.03.14 [그리디, dp]

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

3687번: 성냥개비