알고리즘: 백준 2293번 동전 1 (feat. python)

백준 2293번 링크입니다. 

2293번: 동전 1

 

 

결론부터 말하면 dp를 이용해 풀어야 풀린다. 

 

시간제한이 0.5초로 dp를 제외한 다른 방법을 쓰기가 까다롭다. 

 

처음에는 dfs를 이용해 풀었지만 시간초과가 나길래

 

결국은 다른 분의 답을 참고하였다. 

 

 

 

< 틀렸지만 dfs를 이용한 문제 풀이 > 

 

import sys

class Node:  # 방문처리를 위해 노드 클래스를 만들었다. 
    def __init__(self, data):
        self.data = data

def dfs(start, target, num_list):
    checked = []
    stack = []
    sum = []
    cnt_answer = 0

    stack.append(start)
    sum.append(start.data)
    
    while stack:
        node = stack.pop()
        sum_data = sum.pop()

        if sum_data == k:
            cnt_answer += 1

        if node in checked:
            continue
            
        checked.append(node)

        for num in num_list:
            if sum_data < k and node.data <= num:
                stack.append(Node(num))
                sum.append(sum_data + num)


    return cnt_answer



input = sys.stdin.readline
n, k = map(int, input().split())
num_list = []

for i in range(n):
    num_list.append(int(input()))

answer = 0

for num in num_list:
    answer += dfs(Node(num), k, num_list)
    
print(answer)

 

(사실 인생 첫 dfs를 이용한 문제 풀이라 남기고 싶었다)

 

 

 

 

 

< dp를 이용한 정답 문제풀이 >

 

import sys
input = sys.stdin.readline

n, k = map(int, input().split())
num_list = []
dp = [0 for _ in range(k + 1)]
dp[0] = 1

for i in range(n):
    num_list.append(int(input()))
    
for num in num_list:
    for i in range(1, k + 1):

        if i >= num:
            dp[i] += dp[i - num]

print(dp[-1])

 

dp를 이용하니 너무 간단하게 풀린다. 하지만 개인적으로 어려운 dp문제였고, 

 

dp의 초기 값설정은 아직 완벽하게는 잘 모르겠다. (누구 설명해줄사람 ㅠㅠ)