[백준] 2293번 : 동전1 ( 파이썬, 쉬운 설명, 코린이 버전 ) *이 문제가 너무 어려웠던 코린이는 오세요*

 

디피 자식 ..... 풀어도 풀어도 어려운 너란 유형 .... 자존감 떨어뜨리는 유형

www.acmicpc.net/problem/2293

2293번: 동전 1

 

 디피 문제를 많이 풀어보고 있지만, 풀이를 들었을 때는 솔직히 이해가 갑니다. 하지만, 아직 까지는 스스로 풀어볼 때, 디피를 적용하는 데에는 제 경험이 딸리나 봅니다. 어쩌겠습니까? 못풀면 그 풀이에 대한 해설을 제대로 익히고, 이해하고. 다음에 못풀어도, 또 경험을 쌓다보면, 디피를 조금씩 더 잘 할 수 있지 않을까요?

 

 

우선 이 과목을 수강하기 전 선 수강 과목입니다. 이거 보면 이해가 확 가더라구요. 거기에 저는 좀 더 코린이 전용으로 숟가락을 얹는 풀이를 할 계획이에요. 우선 보고 오세용 

선수 과목 * 필수 시청 * : 개인적으로 블로그에 돌아다니는 모든 풀이를 봤지만, 개인적으로 이것만이 저를 구원해줄 수 있었습니다. 들어보세요, 영상으로 되어있어서 매우 이해하기 편했어요.

https://youtu.be/2IkdAk1Loek

핵심 아이디어 설명 😇

 1원 단위만 썼을 때,

 1,2,3,4,5,6,7,8,9,10원을 만들어봅니다.

 경우의 수가 몇 가지죠?

 

 다 한 가지죠?

 1원 단위만 써서 1원 만들려면 1개, 2원 만들려면 2개, ... 10원 만들려면 10개 이렇게, 목표 ~원에 맞게 1원을 동원하면 됩니다.

 

이제 2원 단위를 하나만 더 동원해보죠. ( <- 이게 핵심. 점점 동전 단위를 하나씩 더 동원해 나가는 거에요. ) 단 !! 이때 2원 단위를 동원한 것이므로, 1원 단위만 사용된 경우의 수는 해당되지 않아요. 명심하세요!! <- 이 포인트를 잊지 마세요

 

두 번째 줄을 보세요, 이제 1원 단위만 가지고 만든 경우의 수 말고, "1원 (&& and 앤드) 2원"을 동원할 때의 경우의 수를 보겠습니다.

 

우선 2원으로 1원을 만들 수는 없어서 0.

2원을 꼭 쓴다고 했을 때, 2원을 만드는 경우의 수는 몇개죠? 2개 아닙니다. 집중하세요 !! 두 개라고 하신 분은

1개죠. 왜냐하면, 이제 1원과 2원을 모두 사용한 경우의 수를 고려하고 있기 때문이에요. 

 

3원을 만들려면요? 그럼? 

3원을 만들려면 현재의 경우, 2원을 무조건 써야하니까, 2원을 무조건 쓴다고 치고, 그러면 조합해내야할 돈이, 1원만 남자나요? 그쵸? 이제 이 1원을

방법1(1원만 쓰기)과

방법2(1원과 2원을 모두 쓰기)로 만들 수 있는 경우의 수

들의 합을 구해주면 됩니다.

그렇다고 하면, 방법1( 1원만으로 1원을 만드는 경우의 수 ) : 1가지

방법2( 1원 2원 모두 동원한 경우의 수 ) : 0가지

를 더해서 써주면 됩니다. 1이죠. 그래서 바로 저 2행 3열에 1이 들어가는 겁니다.

 

이 원리로 쭉쭉 채워넣어봐요 !!

그럼 1,2원 모두 동원하여 4원을 만들려면?

우선 무조건 2원을 써야하니까 2원을 제하여줍니다. 그럼 4-2 => 2원을 방법1과 방법2로 만들면 됩니다.

여기서 1을 취하고

여기서 1을 취한다.

그러면, 방법1과 방법2를 더해서, 2가지가 됩니다.

그 결과를 써주세요

 

결론 : 패턴은 무엇이다? 예를 들어, 5원 단위를 꼭 포함한채로, 1,2,5원 단위로 10원을 만들려면? 우선 5원 단위는 무적권 포함이니 빼주고 시작한다. ( 그럼 1원 만으로 5원 만드는 방법1 / 1,2원 만으로 5원 만드는 방법2 / 1,2,5원 모두 써서 5원 만드는 방법3 ) <- 이 방법 세 가지를 모두 더해준드아 !! 이거였습니다.

( 목표 단위 - 현재 단위 ) 인덱스에서의 <- 이전 단계들의 디피값 + 현재 단계 디피값

 

 

휴 ... 점화식이 드뎌 완성된 것입니다. 이제 코드로 써보세요. 이제 거의다 떠서 드린 것입니다. 코드는 밑에 있어용.

numOfUnits, targetAmount = map( int, input().split() )
units = []
for _ in range(numOfUnits) :
    units.append( int( input() ))

# 두 가지 디피 운영
    # prev_units_total
    # dp
prev_cases_total = [0] * targetAmount 
dp = [0] * targetAmount
firstUnit = units[0]

#
for idx in range( targetAmount ) : 
    if (idx+1) % firstUnit == 0 :
        prev_cases_total[idx] = 1
    else :
        prev_cases_total[idx] = 0

#
for unit in units[1:] :
    for idx in range(targetAmount) :
        if (idx+1) < unit :
            dp[idx] = 0
        elif (idx+1) == unit :
            dp[idx] = 1
        else :
            dp[idx] = dp[ ( idx - unit ) ] + prev_cases_total[ ( idx - unit ) ]
    #
    for k in range(targetAmount) :
        prev_cases_total[k] = dp[k] + prev_cases_total[k]
    

#
print(prev_cases_total[-1])