문제 바로가기
문제:
강산이는 심각한 게임 중독자이기 때문에 날씨에 상관없이 매일 PC방을 간다. 최근에 폭우로 인해 일부 지역이 침수되어 침수된 지역으로는 이동할 수 없게 되었다. 하지만 강산이는 출석 이벤트를 위해 하루도 빠짐없이 PC방을 가야 한다. 강산이는 PC방까지 상, 하, 좌, 우 방향으로만 이동하며, 한 번 이동할 때의 거리는 1이다. 또한, 강산이는 게임을 빨리하러 가야 하기 때문에 집에서 PC방까지 최단경로로 움직인다. 강산이의 집의 좌표 (H, H)와 PC방의 좌표 (N, N)이 주어지고 좌표평면 위 (x, y)에서 y > x인 곳은 침수되었다고 할 때, 강산이가 침수된 지역을 피해서 PC방까지 갈 수 있는 경로의 개수를 구하라. 단, PC방의 좌표가 집의 좌표 같은 경우 경로는 1가지라고 한다.
입력:
첫째 줄에 집과 PC방의 좌표 (H, H), (N, N) 을 나타내는 두 정수 H, N (0 ≤ H, N ≤ 30) 이 차례로 주어진다.
출력:
집에서 PC방까지 갈 수 있는 경로의 개수를 출력한다.
풀이:
import sys
sys.stdin = open('/Users/song/Desktop/Python/Python/h.txt', 'r')
h, c = map(int,input().split())
temp = abs(h-c) + 1
board = [[0]* (temp) for _ in range(temp)]
for i in range(temp):
board[0][i] = 1
for i in range(1, temp):
for j in range(i, temp):
board[i][j] = board[i-1][j] + board[i][j-1]
print(board[-1][-1])
그래프로 그려보면 카탈랑 수 이다.
카탈랑 수 이란 조합론에서 나타나는 수열로 간단히 말하면 대각선을 넘지 않는 경우의 수 이다.
첫 줄을 1로 가득 채운다. 이유는 밑으로 내려갈 수 없어 한 쪽으로 밖에 못가니 한가지의 경우의 수 밖에 안된다.
그다음은 첫번째, 두번째, 세번째 순서대로 채워나가면 된다.
11111
01234
점화식은 왼쪽 + 위에 를 더해주면 현재 위치를 올 수 있는 경우의 수이다.
카탈란 수
카탈란 수 를 사용하면 점화식은 이렇다.
2.
import sys
from math import comb
h, c = map(int,input().split())
d = abs(h-c)
print(comb(d*2,d)//-~d)아래처럼 표현을 할 수 있다고 하는데 모르겠다. 몰라도 될꺼 같다
"~" 는 not 비트 연산자로 d비트를 뒤집은것을 의미한다.
(2n)! //-~d
------ >> comb(d*2,d) 이고 >> (n+1)! 인것 같다.
-n!
3.
def catalan(n):
return math.factorial(2*n) // (math.factorial(n) * math.factorial(n+1))
print(catalan(d))
이렇게 하는게 더 속 편하다.
댓글