백준 22.03.20. 1010번 - 다리 놓기

T = int(input())

dp = [[1] for i in range(31)]

for i in range(1, 31):
    for j in range(i+1):
        if j == 0:
            dp[i][j] == 1
        elif j == i:
            dp[i].append(1)
        else:
            dp[i].append(dp[i-1][j-1]+dp[i-1][j])

for _ in range(T):
    a, b = map(int, input().split())

    if a < b:
        a, b = b, a
    
    print(dp[a][b])

• 결국 서쪽 다리와 동쪽 다리의 조합을 구하는 문제입니다.
• 그리고 출처에 다이나믹 프로그래밍이 포함되어 있길래 dp를 이용해보았습니다.
• dp를 이용하여 파스칼의 삼각형을 만들겁니다.

파스칼의 삼각형 // 위키백과

• 이항의 0제곱일 때는 이항계수가 1이므로 dp의 기본값들을 1로 설정해주었습니다.
• 그리고 N과M이 30까지 주어질 수 있으므로 30제곱의 이항계수까지 구할 수 있도록 범위를 설정했습니다.
• 중첩반복문을 통하여 파스칼의 삼각형을 만들 것입니다.
• 파스칼의 삼각형에서 가장 처음과 마지막 계수는 1이므로 그에 맞게 조건을 설정해주었습니다.
• 나머지 부분(중간부분)은 dp를 이용하여 값을 할당할 수 있도록 했습니다.
• 만들어진 dp를 바탕으로 값을 출력해주면 됩니다.