[Gold IV] 금민수의 합 - 1528

문제 링크

성능 요약

메모리: 104324 KB, 시간: 1168 ms

분류

너비 우선 탐색, 다이나믹 프로그래밍, 그래프 이론, 그래프 탐색

문제 설명

은민이는 4와 7을 좋아하고, 나머지 숫자는 싫어한다. 금민수는 4와 7로만 이루어진 수를 말한다.

N이 주어졌을 때, N을 금민수의 합으로 나타내는 프로그램을 작성하시오. 만약 여러 가지 방법이 존재하면, 수의 개수가 적은 것을 출력한다. 그러한 방법도 여러 개일 경우에는 사전순으로 가장 앞서는 것을 출력한다. 만약 N을 금민수의 합으로 표현할 수 없다면 -1을 출력한다.

N = a1+a2+...+ak가 N = b1+b2+...+bk보다 앞선다는 것은, ai ≠ bi인 가장 작은 i에 대해 ai < bi가 성립한다는 뜻이다.

입력

첫째 줄에 N이 주어진다. N은 1,000,000보다 작거나 같다.

출력

첫째 줄에 정답을 공백을 사이에 두고 출력한다.

풀이

아이디어

가장 먼저 금민수가 될 수 있는 숫자들을 생성하는 함수를 하나 만들어 보았다.

gold_num = set()

def init(s, d):
    if d == 0:
        return
    
    for n in ['4', '7']:
        s += n
        gold_num.add(s)
        init(s, d-1)
        s = s[:-1]

init('', 7)

['4', '7', '44', '47', '74' ...]

두번째 코드는 갯수만 세는 코드인데 다음과 같다.

MAX = 1e9
n = int(input())
gold_num = set()
dp = [MAX]*(n+1)

def init(s, d):
    if d == 0:
        return
    
    for n in ['4', '7']:
        s += n
        gold_num.add(s)
        init(s, d-1)
        s = s[:-1]

def solve(k): 
    if k == 0:
        return 0
    
    if dp[k] != MAX:
        return dp[k]
    
    for g in gold_num:
        if k - int(g) >= 0:
            dp[k] = min(dp[k], solve(k-int(g)) + 1)
    return dp[k]


init('', len(str(n)))
gold_num = sorted(gold_num, key=int)
print(gold_num)
print(solve(n))

마지막은 역추적이다. 선택한 경우 별도의 리스트에 저장하여 선택을 고르도록 하였다.

하지만 단순히 탐색한다면 시간초과의 대환장 파티에 들어갈 수 있다.
새로운 방법을 생각해 봐야 한다.

추가 : 이거 그냥 파이썬이라 안됐던거임.. 정답 코드를봐도 매커니즘은 똑같음.

코드

import sys
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
MAX = float('INF')
n = int(input())
gold_num = set()
dp = [MAX]*(n+1)
rc = [-1] * (n+1)

def init(s, d):
    if d == 0:
        return
    
    for n in ['4', '7']:
        s += n
        gold_num.add(s)
        init(s, d-1)
        s = s[:-1]

def solve(k): 
    if k == 0:
        return 0
    
    if dp[k] != MAX:
        return dp[k]
    
    for g in gold_num:
        if k - int(g) >= 0:
            cand = solve(k-int(g)) + 1
            if cand <= dp[k]:
                dp[k] = cand
                rc[k] = k-int(g)
                
    return dp[k]

res = []
def reconstruct(k):
    if k == 0:
        return
    
    if k != -1:
        res.append(k - rc[k])

    reconstruct(rc[k])

init('', len(str(n)))
gold_num = sorted(gold_num, key=int)
if solve(n) == MAX:
    print(-1)
else:
    reconstruct(n)
print(*reversed(res))

---

회고

숫자가 4와 7 두개로만 표현되기 때문에 이진수로 표현 가능하다.
예를들면 4는 0 7은 1과 같은 식이다