백준 동전 9084 DP

입력은 테스트케이스의 수, 테스트 케이스 별로 주어지는 동전의 개수, 목표 금액 순서로 주어진다.
처음엔 로직을 복잡하게 생각했다.
코인 각각의 배열을 만든 뒤에 반복문 두개를 써서 각각의 코인 값을 병렬적으로 더해나가보려 했다. 대략 수도코드는 아래처럼 생각했다.

for i < n:
	for j < n-i:
		cur = coin[i] + coin[j]
    	if cur >= target:
    		return j+i

근데 글로 풀어보니 이걸로 그다지 논리적인 방법은 아닌것 같아, 이코테 DP강의를 다시 봤다.
결국 중요한건 중복된 부분을 메모로 해결하고 반복을 줄이는건데 위 코드는 그저 반복 그자체..

다시 생각해보자!
메모이제이션 배열의 인덱스는 내가 목표로 하는 target, 즉 cost값을 나타낸다.

• 만약 memo[0]이 주어진다면 이건 가격이 0인 방법이므로 모든 동전을 사용하지 않는다는 1가지 방법이 있다고 하자.
• memo[1]이 주어진다면 이건 가격 1을 만드는 방법이고 딱 하나의 방법이 존재한다. 그러므로 memo[1] = 1이 된다.
• 그런데 더 나아가서 memo[5]를 살펴보자. 가격 5를 만드는 방법은 ' 1+1+1+1+1', '1+1+1+2', '2+2+1' 이렇게 세가지 방법이 주어진다. 그러므로 memo[5] = 3이다.
• 이렇게 각 memo[i]값을 구해나가다 보면 패턴을 발견할 수 있다.

memo[1] = 1
memo[2] = 2
memo[3] = 2
memo[4] = 3
memo[5] = 3
...
memo[5] = 3+2 || 2+2+1 || 5

memo[i] = memo[i] + memo[i-coin]

1트 (Index Error)

1트 작성안에서는 런타임에러가 발생했다!
로직에는 문제가 없다 생각했지만, 주어진 코인값이 cost보다 클때 m이 변경되고 런타임 에러가 발생했다. 이를 처리해주기 위해 다시 코드를 작성했다.

import sys
input = sys.stdin.readline

t = int(input())
for _ in range(t):
    n = int(input()) # number of coins
    coins = list(map(int, input().split())) 
    m = int(input()) # cost

    # memoization
    memo = [0] * (m + 1)
    memo[0] = 1 # 금액 범위 1~10000 초기화

    for coin in coins:
        for i in range(1, m + 1):
            memo[i] += memo[i - coin]

    print(memo[m])

2트 (틀렸습니다)

이건 아예 틀렸습니다가 나왔다.
coins를 돌면서 현재 선택한 동전인 coin이 이전 금액 값들보다 크다면, 더해줄 필요가 없다. 그래서 m과 coin을 비교했었다. 이러면 근데 틀리는게 맞지

import sys
input = sys.stdin.readline

t = int(input())
for _ in range(t):
    n = int(input()) # number of coins
    coins = list(map(int, input().split())) 
    m = int(input()) # cost

    # memoization
    memo = [0] * (m + 1)
    memo[0] = 1 # 금액 범위 1~10000 초기화

    for coin in coins:
        for i in range(1, m + 1):
            if coin > m:
                continue
            else:
                memo[i] += memo[i - coin]

    print(memo[m])

성공! 3트

따라서, 현재 코인 값을 이전 계산 값에 더해가는 조건을 아래와 같이 더 최적화할 수 있다.

import sys
input = sys.stdin.readline

t = int(input())
for _ in range(t):
    n = int(input()) # number of coins
    coins = list(map(int, input().split())) 
    m = int(input()) # cost

    # memoization
    memo = [0] * (m + 1)
    memo[0] = 1 # 금액 범위 1~10000 초기화

    for coin in coins:
        for i in range(coin, m + 1):
                memo[i] += memo[i - coin]

    print(memo[m])