Coding 공부

# 입력 지폐의 금액 T 동전의 가지수 k 각 동전 하나의 금액 pi ni가 주어진다.
# 방법의 수는 2^31 -1 을 초과하지 않는다.



T = int(input())

k = int(input())

money = [list(map(int,input().split())) for _ in range(k)]

money.sort(reverse=True)
dp = (T+1)*[0]

dp[0] = 1
for coin_val,coin_cnt in money:
    for current_money in range(T,1,-1):
        for current_cnt in range(1,coin_cnt+1):
            if current_money - current_cnt*coin_val >= 0:
                dp[current_money] += dp[current_money-current_cnt*coin_val]
print(dp[T])

DP 관련 문제였다. 풀고보니 평범한 배낭과 비슷한 로직이었다. 거기서는 가치를 판단하여, 가치값의 최대를 찾는거였다면, 여기는 방법의 가지수를 찾는 것이라 다르지만, 하나의 dp를 이용해 역으로 진행하면서, 누적시켜주는 것에 있어서 비슷하다고 봤다.

기본적이 원리는 다음과 같다.

동전의 가지수 k개가 주어지면,

첫번째 동전으로 만들 수 있는 모든 동전의 종류를 만들어 본다.

그리고 두번째 동전으로 만들 수 있는 모든 동전의 종류를 만들어서 누적시켜준다.

이렇게 k번을 반복을 해준다.

여기서 주의해야할 점은 아래에서 위로 올라가면, 이전에 만들어진 것 때문에, 원치 않는 결과가 나올 수 있으므로,

주어진 목표 금액인 T에서 -1씩 줄여주면서 다이나믹 프로그래밍을 해준다.

여기서 평범한 배낭과 또 다른 점은, 같은 동전이 여러개 존재하는 것이다.

그래서 동전의 개수 n개만큼 반복을 시켜주면서 진행해야한다.

즉 3원짜리 동전이 5개가 있다하면,

1회차   // 2회차

T - 3*1 ,| (T-1) - 3*1, ....

T - 3*2, |(T-1) - 3*2 ,...

T - 3*3, |(T-1) - 3*3, ...

T- 3*4,  |(T-1) - 3*4 .....

T - 3*5, |(T-1) - 3*5 ....

이렇듯 동전의 개수만큼 진행시켜줘야, 그 동전으로 만들 수 있는 모든 경우를 탐색할 수 있다.

여기서 또 주의해야할 점은 T는 동전의 개수를 조정하는 반복문 밖에 있어야한다.

원래 DP에 약하기도 했지만 비슷한 문제를 풀어본 경험이 있었는데도, 푸는데 시간이 오래걸렸다.

이전에 풀었던 문제들도 다시 공부하여, DP에서 필요한 점화식을 빨리 구하는데 노력해야겠다.

# 5569 출근경로
#  남북방향 도로 w개 동서 방향 도로가 h개
# 남북방향은 서쪽부터 1,2,....w
# 동서도 남쪽부터 1....h
# 교차로 (i,j) 
# 1번 이후부터 가능

w,h = map(int,input().split())
dp = [[[[0]*2 for _ in range(2)] for _ in range(h)] for _ in range(w)]

# 3번째 인덱스 0 북쪽, 1은 동쪽
# 4번째 인덱스는 방향전환 여부 1이 가능 0이 불가능
# 자세한 설명을 하자면, 3번째 인덱스는 그 전 위치에서 올라온 방향을 나타내는 것이다.
# 3번째 인덱스가 0 이면 x-1,y의 위치에서 북쪽으로 올라왔을때를 말한다.
# 4번째 index는 현재 x,y 좌표에 있는 값이 회전이 가능한지에 대해 적어놓은것이다.
# 1이면 회전이 가능한 것이고, 0이면 회전이 불가능한 것이다.

# 처음에, x=0일때와 y=0일때 초기화 작업을 해준다.
for i in range(1,w):
    dp[i][0][0][1] = 1
for i in range(1,h):
    dp[0][i][1][1] = 1


for x in range(1,w):
    for y in range(1,h):
        # (x,y) 좌표에서 3번째 index가 0 인 경우는 (x-1,y)에서 온 경우이다.
        # 여기서 회전이 가능할때와 불가능할때를 구분해서 해야한다.
        # 회전이 불가능한 경우는 (x-1,y) 위치에서 3번째 index가 1이고, 네번째 index가 1인경우이다.
        # 동쪽에서 오고, 회전이 가능할때이다. 북쪽으로 방향이동을 할수 있고, 그 다음에는 방향을 전환할수 없기 떄문이다.
        # 회전이 가능한 경우는 (x-1,y) 기준으로 3번째 index가 0인 경우 전부이다.
        # 왜냐하면 (x-1,y)에서 3번째 index가 0인경우는 (x-2,y)에서 온 경우이므로, 어떠한 경우에서도 회전이 가능하기 때문이다.
        dp[x][y][0][0] = dp[x-1][y][1][1]
        dp[x][y][0][1] = dp[x-1][y][0][0] + dp[x-1][y][0][1]
        # (x,y) 좌표에서 3번째 index가 1인 경우는 (x,y-1)에서 온 경우이다.
        # 여기서 회전이 가능할때와 불가능할때를 구분해야한다.
        # 회전이 불가능한 경우는 (x,y-1) 위치에서 3번째 index가 0이고, 네번째 index가 1인 경우이다.
        # (x,y-1)으로 올때 (x-1,y-1)에서 올라와서 방향전환을 (x,y-1)에서 해서 방향전환을 할 수 없기때문이다.
        # 회전이 가능한 경우는 (x,y-1) 위치에서 3번째 index가 1인 모든 경우이다.
        dp[x][y][1][0] = dp[x][y-1][0][1]
        dp[x][y][1][1] = dp[x][y-1][1][0] + dp[x][y-1][1][1]
result = sum(dp[w-1][h-1][0]) + sum(dp[w-1][h-1][1])
print(result%100000)

다이나믹 프로그래밍를 이용해 푼 문제 중에서 내게 어려웠던 문제였다.

DP를 잘 모르는 상태에서 DP를 어떻게 설계를 해서, 저장시켜놓을지가 고민이었다.

그리고 여기서 좀 헷갈렸던 것이, DP에 이전 위치에서 올라온 방향을 저장해주는 3번째 index와, 회전이 가능한지 구분해주는 4번쨰 index가 헷갈렸다.

회전이 가능한 것은 현재 (x,y) 좌표에서 회전 가능여부를 보는 것이고, 3번째 index는 그 전 위치에서 북쪽에서 왔는지 동쪽에서 왔는지 구분해줘야했다.

서로 다른 기준점으로 인해, DP를 설계하는데 어려움을 겪었다.

위의 코드의 주석에서도 설명했지만, 총 4가지 경우를 나누어서, 정리해야한다.

1. 이전 위치에서 북쪽으로 이동해서 도착했고,, 다음번에 회전이 가능한 경우

2. 이전 위치에서 북쪽으로 이동해서 도착했고, 다음번에 회전이 불가능한 경우

3. 이전 위치에서 동쪽으로 이동해서 도착했고, 다음번에 회전이 가능한 경우

4. 이전 위치에서 동쪽으로 이동해서 도착했고,다음번에 회전이 불가능한 경우

1번 경우를 설명하자면, (x,y) 위치에 올때, 북쪽으로 이동해서 도착하고, 회전이 가능할려면, (x-1,y)에서 와야하며, 거기서도 북쪽으로 도착해야지만, 쭉 직진으로 온거기 때문에 회전이 가능하다.

이러한 경우는 [x-1][y][0][0]와 [x-1][y][0][1] 이다. 인덱스를 분석하면

[x-1][y][0][0]은 x-2,y의 위치에서 x-1,y로 북쪽으로 해서 왔고, x-2,y의 위치에서 이미 방향을 전환했기때문에, x-1,y에서 방향전환을 못하는 빨강색 화살표를 의미한다.

[x-1][y][0][1] 은 x-2,y의 위치에서 x-1,y로 북쪽으로 해서 왔고, x-2,y에서 방향전환을 안하고 왔기 때문에, x-1,y의 위치에서 방향전환이 가능한 파랑색 화살표를 의미한다.

그러므로 [x][y][0][1] = [x-1][y][0][0] + [x-1][y][0][1] 이다.

2번 경우는 (x-1,y)에서 방향전환을 해서 (x,y)를 왔기 때문에 다음번에 회전을 못하는 경우이다.

이런 경우는 (x-1,y)에서 동쪽에서 왔고, (x-1,y)에서 회전이 가능한

[x-1][y][1][1] 일때, [x][y][0][0]이 될수 있다.

3,4번 경우는 위를 회전한 것이다.

그림이 조잡해서 약간 이해하기 힘들지만, 위와 같이 총 4가지 경우를 나누어서 dp를 하면 된다.