[BOJ] 2293번: 동전 1 (DP)

 

(( 한 번 더 보기 ))

 

문제 링크

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

 

 

 

TIL

• 이렇게 문제에서 연속되지 않지만, 사용해야하는 원소가 주어지면 (이 문제에서는 가치가 다른 임의의 개수의 동전)
  • for c in coin 과 같이 해당 원소를 기준으로 순회하는 방법을 떠올리기 !!
• dp에 저장하는 값은 문제에서 요구하는 값임 !!!!!!!!! 
  • 여기서는 만들 수 있는 경우의 수가 됨
• 처음에 tabulation을 사용하기에 k의 범위가 크고, 물어보는 것이 딱 하나에 대한 결과여서 memoization을 생각함. (Top-down)
  • 시간제한이 0.5 초 (추가 시간 없음)인데 지금 코드는 O(nk)니까 최대 100,000번. 따라서 시간초과발생할거라 생각
  • 근데 일단 tabulation(bottom-up)으로도 동작 아주 잘함~
  • top down으로는 이상하게 중복을 처리하는 게 잘안됨 ㅜㅜ 
• 근데 처음에 생각한 대로 tabulation / memoization 두 개 중에 선택하는 거 맞음
• DP 사용방식 외우기 !!
• dp[0] = 1 설정
  • 특히 조합 문제나 누적합 문제에서 자주 사용
  • 부분 문제의 기본값을 설정할 때, dp[0] = 1은 매우 자주 사용. 예를 들어, 동전 문제나 배낭 문제에서 0을 만드는 방법은 "아무 것도 선택하지 않는 방법"이기 때문에 그 경우의 수는 1.
• dp[0] = 1 미설정
  • 예를 들어, 최소값 구하기와 같은 문제에서는 dp[0] = 1이 맞지 않을 수 있음
  • dp[0] = 1을 사용하면 해가 없는 경우에 문제가 발생할 수 있기 때문에, 문제의 성격에 맞게 적절히 설정

 

 

 

Code

[ Bottom-up / Tabulation ]

n, k = map(int, input().split())

dp = [0]*(k+1)
coin = [int(input()) for _ in range(n)]
dp[0]=1

for c in coin:
    for j in range(c, k+1):
        dp[j] += dp[j-c]

print(dp[k])

• 중복을 고려하지 않고 경우의 수를 세야함
  • 따라서 범위를 (c, k+1) 로 해서 c이상의 코인만 보도록 함