[BaekJoon 10146 : 동적계획법, Python] - 격자상의 경로

2021, Nov 02    


백준 10146 격자상의 경로 : 실버 1



Solution


import sys
input = sys.stdin.readline

n, m, k = map(int, input().split())
if n == 1 or m == 1:
    print(1)
    sys.exit(0)

if k == 0 :         
    n1, m1, n2, m2 = n, m, 0, 0
else:
    if k%m == 0:            # 각 행의 마지막 열
        n1, m1 = k//m, m
    else: 
        n1, m1 = k//m + 1, k%m
    n2 = n - n1 +1
    m2 = m - m1 +1

def findPath(n, m):
    if n == m == 0:
        return 1
    if n ==1 or m == 1:
        return 1

    tot = n*m
    DP = [0 for _ in range(tot + 1)]
    DP[1] = 1

    for i in range(2, tot + 1):
        if i%m == 1:            # 각 행의 첫 번째 열
            DP[i] = DP[i-m]
        elif i//m == 0 or (i//m == 1 and i%m == 0):         # 첫 번째 행
            DP[i] = DP[i-1]
        else:
            DP[i] = DP[i-m] + DP[i-1]
    return DP[tot]

print(findPath(n1, m1)*findPath(n2, m2))


풀이과정 및 느낀점


케이스를 나누는 게 꽤 까다로운 dP 문제였다.
우선 k 가 0 인 경우와 그렇지 않은 경우로 나누고, k 의 위치를 기준으로 격자를 나누고, 각 두 격자의 끝 값까지 도달하는 경우의 수를 곱해서 최종적으로 출력한다.
k 가 0인 경우는 그냥 n1, m1, n2, m2 = n, m, 0, 0 으로 설정하고,
k가 0이 아닌 경우, k의 위치가 각 행의 마지막 열에 있는 경우와(n1, m1 = k//m, m) 아닌 경우로 (n1, m1 = k//m+1, k%m) 또 나누어서 두 격자의 위치를 나눈다.
경로를 찾는 findPath 함수 내에서 n, m 이 0 으로 들어오거나, n, m 중 적어도 하나가 1이라면 경우의 수는 1개밖에 없으니 1을 return 하고, 아닌 경우에는 DP 값을 갱신해준다. (1. 각 행의 첫번째 열, 2. 첫번째 행, 3. 그렇지 않은 경우로 나누어서 갱신)
DP[1] = 1 로 설정하고 for 문을 2번째 idx 부터 돌리기 때문에 1번 케이스와 2번 케이스가 겹칠 일은 없다.
이 문제는 특이하게 서브케이스가 나누어져있고, 제출하게 되면 오답 or 정답이 아닌 점수가 부여되는데, 처음에는 32점이 계속 나오다가 k 가 각 행의 마지막 열에 있는 경우에 대한 예외처리를 해줘서 100점이 나왔다.
꽤 재밌는 DP 문제였다.

# BaekJoon # Python # DP # 동적계획법 # Dynamic Programming # Algorithm