[파이썬] 백준 3687: 성냥개비 (골드2)

[파이썬] 백준 3687: 성냥개비 (골드2)

 

3687번: 성냥개비

---

문제

---

풀이

0. 방향성 생각

• 최대값은 가장 적은 수를 사용해서 앞에 붙여서 가장 큰 자리수로 만들어준다.
• 최소값은 DP를 사용해서 자연수 n = k + (n-k)로 분리한다.

 

1. 입력

import sys
input = lambda : sys.stdin.readline().rstrip()

use = [int(input()) for _ in range(int(input()))]
dp = [0]*101
dp[:10] = [0,0,1,7,4,2,0,8,10,18]

DP 초기값을 10까지 할당해준다.

 

2. 최소값은 DP

for n in range(10,101):
    temp = []
    for k in range(2,n+1):
        if k==6: temp_n = '6'+str(dp[n-k])
        elif n-k == 6: temp_n = str(dp[k]) +'0'
        else: temp_n = str(dp[k]) +str(dp[n-k])
            
        if temp_n[0] != '0':
            temp.append(int(temp_n))
    dp[n] = min(temp)
dp[6] = 6

 

3. 최대값은 그리디

for n in use:
    p,q = divmod(n,2)
    if q: max_n = int('7'+(p-1)*'1')
    else: max_n = int('1'*p)
    print(dp[n],max_n)

가장 적은 개수를 사용해서 자리수를 늘려주면 된다.

성냥개비가 짝수개이면 모두 1로 처리한다. 

홀수개이면 한개는 7로 3개를 쓰고 남은 개수를 1로 처리한다.

---

전체코드

import sys
input = lambda : sys.stdin.readline().rstrip()

use = [int(input()) for _ in range(int(input()))]
dp = [0]*101
dp[:10] = [0,0,1,7,4,2,0,8,10,18]

for n in range(10,101):
    temp = []
    for k in range(2,n+1):
        if k==6: temp_n = '6'+str(dp[n-k])
        elif n-k == 6: temp_n = str(dp[k]) +'0'
        else: temp_n = str(dp[k]) +str(dp[n-k])
            
        if temp_n[0] != '0':
            temp.append(int(temp_n))
    dp[n] = min(temp)
dp[6] = 6

for n in use:
    p,q = divmod(n,2)
    if q: max_n = int('7'+(p-1)*'1')
    else: max_n = int('1'*p)
    print(dp[n],max_n)

 

코멘트

6일때만 처리 잘해주면 된다.

k 범위를 절반으로 줄이는거랑 효율성을 조금 늘릴 수 있는 부분이 보이긴 하는데 패스...