2293. 동전1

문제

백준 2293번 동전1

---

풀이

또 생각없이 dfs로 풀었다. 어김없이 RecursionError 당했다.
이제 좀 dfs 트라우마 생기려함.

def dfs(L, val):
  global cnt
  if val == k: 
      cnt += 1
  if val > k or val+coins[L] > k: return
  else:
      for i in range(L, len(coins)):
          dfs(i, val + coins[i])
        
if __name__ == '__main__':
  n, k = map(int, input().split())
  coins = [int(input()) for _ in range(n)]
  cnt = 0
  dfs(0, 0)
  print(cnt)
  

도저히 방법을 모르겠어서 알고리즘 분류를 봤다. 동적프로그래밍이었다...

다음과 같이 동적 배열을 구할 수 있다.

공간 효율을 위해 2차원 리스트 대신 1차원 리스트를 갱신하며 사용했다.

n, k = map(int, input().split())
coins = [int(input()) for _ in range(n)]
dy = [0] * (k+1)
for c in coins:
    for i in range(c, k+1):
        dy[i] = dy[i] + dy[i-c] if i-c > 0 else dy[i] + 1
print(dy[k])

---

부족한 점

기본 문제였는데 아직 알고리즘 전반적으로 부실한 느낌이다.
기본 알고리즘 습득을 위해 반복 구현을 통해 익혀야겠다.