백준 1010 풀이 (다리 놓기, 다이나믹 프로그래밍)

오우 진짜 나 수학적 지식이 부족한게 너무 뼈저리게 느껴졌다ㅋㅋㅋㅋㅋㅋㅋㅋ

이거 일일히 다리 그리면서 안겹치게 하려면 어떻게 해야하나 규칙찾고 있었다.....ㅋㅋㅋㅋㅋ

하...그러다가 먼가 조합스러워서 조합계산기를 돌려보니까 그냥 조합 문제였다.

그래서 11051 문제에서 사용했던 DP로 조합구하는 코드를 사용해서 미리 연산을 통해 필요한 조합값들을 구하고 필요할때 부르는 방식으로 코딩을 진행했다.

 

시간 제한이 0.5초라 이러한 방식이 효율적이라 판단했다.

memo  = [[0 for i in range(30+1)] for i in range(30+1)]

memo[1][0] = 1
memo[1][1] = 1
for i in range(2,30+1):
    memo[i][0] = 1
    for j in range(1,i):
        memo[i][j] = memo[i-1][j-1] + memo[i-1][j]
    memo[i][i] = 1
n = int(input())
for i in range(n):
    a,b = map(int, input().split())
    print(memo[b][a])

어쩐지 정답비율이 높더라니.....수학의 정석 한번 봐야하나.....