[코딩테스트] 백준 다리 놓기(1010) 파이썬(Python)

https://www.acmicpc.net/problem/1010

1010번: 다리 놓기

t = int(input())
d = {}
for i in range(1,30+1):
    for j in range(i,30+1):
        if i == 1:
            d[(i, j)] = i * j
        elif i == j:
            d[(i, j)] = 1
        else:
            d[i, j] = d[(i, j-1)] + d[(i-1, j-1)]
for _ in range(t):
    n, m = map(int, input().split())
    print(d[(n, m)])

점화식을 세우고 다이나믹 프로그래밍으로 문제를 해결하였습니다.

먼저 값을 저장할 딕셔너리 자료구조(d)를 생성해줍니다.

 

점화식은 아래와 같습니다.

• (2, 3) = (2, 2) + (1, 2)
• (2, 4) = (2, 3) + (1, 3)
• ...
• (3, 4) = (3, 3) + (2, 3)
• (3, 5) = (3, 4) + (2, 4)
• ...
• (n, m) = (n, m-1) + (n-1, m-1)

현재 경우의 수는 강의 동쪽 사이트에서 하나 뺀 경우의 수와 서쪽과 동쪽에서 모두 하나 뺀 경우의 수를 합친 경우의 수와 동일합니다.

 

알고리즘은 아래와 같습니다.

나올 수 있는 강의 서쪽, 동쪽 사이트이 모든 경우의 수를 미리구하여 저장합니다.

n, m이 입력으로 들어왔을 때 매번 계산하는 계산 과정을 줄여줍니다.

 

이때 i는 서쪽 사이트에 해당하며 1부터 시작하여 30까지 순회하며 j는 동쪽 사이트로 i보다 크거나 같아야 하기 때문에 

i부터 시작하여 30까지 순회합니다.

 

i = 1이라면 즉 강의 서쪽에 위치한 사이트가 1개라면 j만큼의 경우의 수를 저장합니다.

i와 j가 동일하다면 한가지 경우의 수 밖에 없기 때문에 1을 저장합니다.

 

위의 두 조건에 만족하지 않는다면 위의 점화식을 적용하여 경우의 수를 계산하여 적용합니다.

 

문제에서 주어지는 입력을 받고 d에서 서쪽, 동쪽 경우의 수를 찾아서 반환하면 됩니다.