문제

others

1. 전체를 부분 문제로 잘 나누었는가 (부분문제의 점화식)
2. 부분 문제를 잘 풀면서 메모이제이션을 잘 하였는가
3. 해당 점화식은 부분 문제 사이의 관계를 잘 표현했는가

해당 문제는 가치의 합이 k가 되는 조합
즉, 부분 문제는 가치의 합이 i가 되는 조합(1=<i<=k) 찾기 > 특정 동전을 썼을 때 가치의 합이 i가 되는 것 찾기
메모리는 4mb밖에 안되므로 배열 하나로 해야 한다.
출처

n, k = map(int, input().split())
c = []
dp = [0 for i in range(k + 1)]
dp[0] = 1
for i in range(n):
    c.append(int(input()))
for i in c:
    for j in range(1, k + 1):
        if j - i >= 0:
            dp[j] += dp[j - i]
print(dp[k])

1. 특정 가치에서 현재 동전을 빼도 0이상인가 (현재 동전으로 가치 합 찾을 수 있는지)
   1-1. 가능하다면 이전 가치 경우의 수를 더해주기

• if j-i>=0 : do[j]+=dp[j-i]
  i가 j-i에서 0 이상이면 해당 가치는 j-i 가치의 경우의 수 + 현재까지의 j의 경우의 수이다.
  i가 2이고 j가 7이면, 7일때 경우의 수에 5(7-2)일때 경우의 수를 더 해준 것이라는 것
  7을 만들기 위해 2+5가 가능하니 5일때 경우의 수에 2가 더해지면 7이니 7을 만들 수 있는 경우의 수가 하나 늘어나는 것.
  (맞나..?)
  
  출처

🥺🥲😭