[TIL_Carrotww] 99 - 23/02/10

📝Carrotww의 코딩 기록장

🧲 python algorithm

🔍 programmers 거스름돈 - Level3

• 첫 번째 풀이

def solution(n, money):
    temp = []

    def dfs(index, change):
        if n == change:
            temp.append(1)
            return
        if n < change:
            return
        for i in range(index, len(money)):
            dfs(i, change + money[i])

    for i in range(len(money)):
        dfs(i, money[i])

    return len(temp) % 1000000007

순열로 풀이했다.
brute force로 풀이한 것이다. 문제를 딱 보고서는 그냥 돌리면 답 나오겠다~ 싶어서
brute force로 일단 풀었는데 정롹성 테스트는 통화했지만 효율성 테스트에서 모두 실패하였다.

dp 로 풀어야 된다는걸 알고
dp 배열에 인덱스에는 해당 돈을 써두고 반복문을 돌려 해당 돈에 나오는 조합을
갱신하는 식으로 풀이했다.

• dp 풀이

def solution(n, money):
    dp = [0 for _ in range(n + 1)]
    dp[0] = 1

    for mon in money:
        for i in range(mon, n + 1):
            dp[i] = (dp[i] + dp[i - mon]) % 1000000007
    return dp[-1]

dp 문제를 너~~무 오랜만에 풀어서 풀이를 접근할때 생각조차 못했다.
역시 계속해서 문제를 풀어봐야한다 ㅠㅠ