[TIL][Krafton Jungle] 3주차 - (4) : DP 알고리즘 적용의 연습

현재 컴퓨터 시스템을 공부하고 있는 내용은 이해할 내용이기보다는

어셈블리어의 인스트럭션 기호의 정의와 해석적인 파트를 읽고 있어서, 따로 정리하지는 않겠다.

 

대신 DP 알고리즘을 이용한 간단(?)하지만, 코드화(규칙화)하기 힘든 문제를 통해서

DP 문제 풀이에 조금 더 익숙해져보자.

 

---

 

BaekJun - #9084 : 동전 (DP)

동전 0 이랑 비슷해 보이지만 이문제는 DP 문제이다.

 

동전 단위가 주어지고 해당 값을 만들 수 있는 경우의 수를 출력하는 문제인데,

문제 아이디어를 떠올리기가 역시 아직 쉽지 않다.

 

처음엔 01타일 문제를 먼저 떠올렸다.

 

가장 최근에 푼 01타일 문제를 겪은 후에

'베이스케이스를 찾아서, 그 케이스를 통한 확장에 대한 문제가 DP구나.' 라고 생각했었는데,

이 문제를 통해서 다시 Knapsack 문제가 떠오르면서, 아이디어의 폭이 좀 더 유동적이게 바뀔 수 있었던 것 같다.

 

문제 아이디어는 다음과 같다.

 

목표 금액을 index로 하는 dp 리스트를 선언한 뒤,

dp 리스트 인덱스 하나하나에 작은 단위의 동전부터 만들 수 있는 경우의 수를 더해 간다.

 

처음에 2원짜리로 리스트를 기록한다면

2 , 4 , 6 , 8 , 10 인덱스(목표금액이 10원이라고 가정하자)에 1이라는 값으로 수정될 것이다.

그 이후 3원짜리로 기록하게 되면 3,6,9는 당연히 +1이 되겠지만,

2+3 = 5도 고려해서 +1을 해주어야 한다.

 

따라서 기록할때, dp[i] + = dp[i-현재 동전의 값]으로 수식을 선언하면

5의 인덱스 때에 3으로 경우의 수를 기록할때, 5-3 = 2 인덱스에서

2로 기록했을 당시 1이었던 값이 5에 기록되면서 계속 리스트를 갱신 할 수 있을 것이다.

 

내가 작성한 코드는 다음과 같다.

import sys

testCase = int(sys.stdin.readline())
result = []
for i in range(testCase):
    Coins_num = int(sys.stdin.readline())

    Coins = list(map(int,sys.stdin.readline().split()))

    goal_coin = int(sys.stdin.readline())
    dp_list = [1]+[0 for _ in range(goal_coin)] ## 동전이 처음 인덱스를 만날때, +1해주기 위해서
    for i in range(len(Coins)):
        This_Coin = Coins[i]
        for j in range(This_Coin,goal_coin+1):
            dp_list[j] += dp_list[j-This_Coin]
    result.append(dp_list[goal_coin])

for answer in result:
    print(answer)

 

리스트에 값들을 더해가며 최종의 값을 구한다는 것이 DP의 유형과 꽤 잘 맞아서,

이 방식도 앞으로 DP를 접했을 때, 고려해 볼만 하다고 생각했다.

---