척척석사의 코딩기록

즉, 제한된 금액을 기반으로 최대의 숫자를 만들어내는 프로그램을 작성하는 것이 되겠다.

스펙은 다음과 같습니다.

파이썬에서는 그래도 나름 괜찮은 퍼포먼스였던 것 같다. 메모리를 더 줄일 수 있다면 좋을 것 같다.

그리고 작성한 프로그램은 다음과 같다.

N = int(input())
value = list(map(int,input().split()))
M = int(input())

dp = [-1 for _ in range (0, 51)]

for i in range (0,N):
    if M - value[i] >= 0:
        dp[M-value[i]] = max(dp[M-value[i]], i)

for i in range (50,-1,-1):
    if dp[i] != -1:
        main_number = str(dp[i])
        for j in range (0,N):
            if i - value[j] >= 0:
                new_number = main_number + str(j)
                dp[i - value[j]] = max(dp[i - value[j]], int(new_number))

ans = max(dp)
print(ans)

이 방법은 냅색 문제와 비슷한 느낌으로 풀었던 것 같다.

dp라는 array를 만들어 둔 뒤, 각각의 index가 "보유한 돈"을 나타낸다고 생각하자.

그리고 dp[index]는 보유한 돈을 바탕으로 가장 큰 수를 나타낸다고 하자.

첫번째 반복문에서 "한자릿수"의 카드들을 먼저 배치하는 상황이 되겠다.

두번째 반복문은, 50 -> 0 순으로 가지고 있는 돈이 적어지는 순으로 반복이 진행된다고 생각하면 좋을 것 같다.

무엇인가를 사는 이상 보유한 돈은 반드시 줄어들기 때문이다.  (마치 monotonically decreasing 같다)

main_number는 보유한 돈이 i일때 나타낼 수 있는 최대 숫자를 나타내고,

new_number는 이 최대 숫자 뒤에 어떤 숫자를 붙일 수 있을지 판단하면서 i - value[j]의 값과 대소를 비교하게 되겠다.

그리고 마지막으로 dp값에서 가장 큰 것을 찾아주면 되겠다.