[알고리즘] 백준 1010 다리놓기

1. 문제

다리 놓기

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

 

2. 접근

1. 문제를 손으로 풀다보면 반복되는 연산 구조를 볼 수 있다.

2. 그 연산구조에서 2가지 방법을 볼 수 있는데, 일반적으로 수학적으로 푸는 방법, DP 로 푸는 방법이 있다.

 

- 수학

nCm 의 방법을 쓰면 되는데, 우리가 쓰는 combination은 보통 리스트에서 사용을 한다.

 

하지만, 우리는 여기서 정수로 input을 받기에 combination이 아닌, nCm = m! // ((m-n)! * n!) 이 방법을 쓰면된다

두개의 정수 n,m을 map 함수로 받아서 적용하면 된다.

 

참고로 factorial은 math.factorial 도 되고, factorial 험수를 만들어도 된다

 

참고,

def fact(n):
    num = 1
    for i in range(1, n+1):
        num *= i
    return num

 

- DP

DP는 2차원 배열을 초기화 해보자

두개의 정수를 받고 그 정수를 2차원 배열의 행과 열로 하며, 0으로 초기화한다

    west, east = map(int, input().split())
    dp = [[0 for _ in range(east+1)] for _ in range(west+1)]

 

참고로 문제에서 보면 " 서쪽의 다리 개수 <= 동쪽의 다리 개수 " 임을 알고 풀자

서쪽과 동쪽의 다리의 개수가 같은지, 서쪽의 다리개수 == 동쪽의 다리 개수 인지를 2중 for문 속에서 체크를 먼저해준다

 

그리고 서쪽의 다리 개수 < 동쪽의 다리 개수 일때를 조심해야하는데, 초기화한 2차원 배열을 보면 dp[w][e] = dp[w][e-1] + dp[w-1][e-1] 임을 알 수 있다

   for i in range(1, west+1):
        for j in range(1, east+1):
            if i == 1:
                dp[i][j] = j
                continue
            if i == j:
                dp[i][j] = 1
            else:
                if j > i:
                    dp[i][j] = dp[i][j-1] + dp[i-1][j-1]

 

 

3. 풀이

# 다리 놓기
import sys
input = sys.stdin.readline


# def fact(n):
#     num = 1
#     for i in range(1, n+1):
#         num *= i
#     return num


# for tc in range(int(input())):
#     # 서쪽 -- 동쪽 사이트의 개수
#     westBridge, eastBridge = map(int, input().split())

#     bridge = fact(eastBridge) // (fact(eastBridge -
#                                        westBridge) * fact(westBridge))

#     print(bridge)

for tc in range(int(input())):
    west, east = map(int, input().split())
    dp = [[0 for _ in range(east+1)] for _ in range(west+1)]

    for i in range(1, west+1):
        for j in range(1, east+1):
            if i == 1:
                dp[i][j] = j
                continue
            if i == j:
                dp[i][j] = 1
            else:
                if j > i:
                    dp[i][j] = dp[i][j-1] + dp[i-1][j-1]
    print(dp[west][east])