백준 1010 다리 놓기 [개인적인 풀이 과정]

N과 M에 1 ~ 7까지 넣어 본 값을 나타내서 규칙을 찾았다.

M과  N이 같을 경우 1, N이 1일 경우 M랑 같은 수 출력, 그 외에 N과M이 입력될 경우 (N에 M-1이 입력된 경우) + (N-1에 M-1이 입력된 경우)와 같다. 

 

이는 실제로 사이트를 그려보면 나오는데 

2 2가 입력될 때 갈 수 있는 경우의 수는 1개이며

2 3이 입력될 경우 기존 경우(2 2입력)가 겹치지 않아야 되기 때문에 맨 위의 사이트를 위에 고정시킨 상태로 아래 사이트를 움직일 수 있는 경우의 수와 같기 때문이다.

 

규칙은 찾았는데 이것을 코드로 어떻게 표현할지가 막막하다.

피보나치 수열 관련해서 나왔을 때랑 비슷한 방법으로 풀면 될 것 같은데 제대로 숙지 된 내용이 아니라 스스로 구현은 하지 못했다.

 

https://li-fo.tistory.com/60 huibum님의 블로그를 참조하여 비슷한 문제가 다가올 때 풀 수 있도록 대비했다.

파이썬 | 백준 | 1010 | 다리 놓기

규칙은 i = j, i = 1, i <j 세가지 경우로 나눠서 나타난다.

import sys

t = int(sys.stdin.readline())
dp = [[0]*30 for _ in range(30)]     # dp 테이블 만들기



for i in range(30):            # 0~ 29까지 반복   (N과 M의 범위)
    for j in range(30):        # i 0 j0~29, i 1 j 0~29
        if i == 1:
            dp[i][j] = j
        else:
            if i == j:
                dp[i][j] = 1
            elif i < j:
                dp[i][j] = dp[i-1][j-1] + dp[i][j-1]

for i in range(t):
    n, m = map(int, sys.stdin.readline().split())
    print(dp[n][m])

import math

T = int(input())

for _ in range(T):
    n, m = map(int, input().split())
    mCn = math.factorial(m) // (math.factorial(n) * math.factorial(m - n))
    print(mCn)

math를 이용하면 이렇게 짧게 풀린다.

해당 문제에서 다리끼리 겹칠 수 없는 다리를 지을 수 있는 모든 경우의 수를 구하므로 조합을 사용하여 풀 수 있다.

nCr = n! / r! * (n-r)! 을 이용하면 바로 답이 나온다.

 

다양하게 넣어봤는데 dp를 이용한 것이 math이용, 혹은 factorial 함수 선언 이용 한것 보다 시간상 제일 빨랐다(68ms)