[Python] 백준 #20152- Game Addiction

문제

---

20152번: Game Addiction

코드

---

My answer

import sys
input=sys.stdin.readline

h,n=map(int,input().split())
if(n>h):
    h,n=n,h
dp=[]

for i in range(h+1):
    dp.append([0]*(i+1))

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

Another answer

H, P = map(int, input().split())
N = max(H, P) + 1
maps = [[0] * N for _ in range(N)]
if H > P:
    H, P = P, H
if H == P:
    print(1)
else:
    maps[H][H] = 0
    for i in range(H, P+1):
        maps[i][H] = 1
    for i in range(H+1, P+1):
        for j in range(H+1, P+1):
            if j > i: continue
            maps[i][j] = maps[i-1][j] + maps[i][j-1]
    print(maps[P][P])

from math import*
h,n=map(int,input().split())
d=abs(h-n)
print(comb(d*2,d)//-~d)

풀이

---

나는 어릴 때 수학문제 풀던 방식을 이용해서 규칙을 찾아냈다. 한 좌표에서 다른좌표까지의 최단거리를 찾던 방법을 그대로 식으로 만들어서 사용했다. 두번째 코드는 내 코드와 아예 동일한 방법을 좀더 깔끔하게 정리한 것이길래 가져와봤고 마지막 방법은 도저히 이해가 안가서 찾아보니 카탈란수열?을 이용했다고 한다. 궁금하신 분들은 카탈란수열에 대해서 공부해보길 바란다.

카탈란 수(catalan number)