[백준] 동전1 파이썬 풀이(DP)

 

백준 2293번 동전1을 풀어보았다.

https://www.acmicpc.net/problem/2293

처음엔 백트래킹으로 풀어보았고, 그다음에는 stack을 이용해서 풀어보았지만 둘다, 시간초과, 또는 메모리 초과가 되어 맞았는지 어쨌는지 알 수가 없었다.

백트래킹으로 풀어 본 풀이

def main():
    N, goal = map(int,input().split())
 
    coin = []
 
    for i in range(N):
        coin.append(int(input()))
    
    coin = sorted(coin, reverse = True )
 
 
    cnt = 0 
    # print(coin)
    def do(money_sum, index):
        nonlocal cnt 
        if index < len(coin):
            temp = 0
            while 1:
                if(money_sum + coin[index]*temp==goal):
                    cnt +=1
                    break
                    
                elif(money_sum + coin[index]*temp<goal):
                    do(money_sum+coin[index]*temp, index+1)
                    temp +=1
                else:
                    break
 
    do(0,0)
        
    print(cnt)
 
 
 
 
 
if __name__ == "__main__":
    main()

 

스택을 이용해서 풀어본 풀이

 
 
def main():
    N, goal = map(int,input().split())
 
    coin = []
 
    for i in range(N):
        coin.append(int(input()))
    
 
    coinstack = [0]
    cnt =0 
    
    for num in coin:
        # print(num)
        coinstack, cnt =addto(coinstack, num, goal, cnt)
 
 
    print(cnt)
   
def addto(coinstack, num, goal,cnt):
    newstack = []
 
    while coinstack:
        currsum = coinstack.pop(0)
        temp = 0
        while 1:
            if(currsum + num*temp==goal):
                cnt +=1 
                break
            elif(currsum + num*temp<goal):
                newstack.append(currsum + num*temp)
                temp +=1
            else:
                break
    # print(newstack, cnt)
    return newstack, cnt
    
 
 
 
 
 
if __name__ == "__main__":
    main()

 

그래서다른 사람의블로그를 참고하여 dp로 푸는 방법을 이해했고, dp로 풀어보았다.

https://marades.tistory.com/5 (참고한 블로그)

내가 본 dp중에 까다로운 편에 속하는 것 같다.

 

정답 풀이

 
import sys 
 
def main():
    N, goal = map(int,sys.stdin.readline().split())
 
    coins = []
 
    for _ in range(N):
        coins.append(int(sys.stdin.readline()))
 
    dp = [0 for _ in range(goal+1)]
    dp[0] = 1 
    for coin in coins:
        for i in range(coin, goal+1):
            dp[i] += dp[i-coin]
 
    print(dp[goal])
 
 
 
 
if __name__ == "__main__":
    main()