[python/파이썬] 백준 20152 Game Addiction

[문제 출처]

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

20152번: Game Addiction

 

 

[문제 풀이]

집과 PC방의 좌표는 x와 y의 값이 같기에 h와 n값이 무엇이냐보다는 두 값의 차이가 얼마이냐가 중요하다.

두 값이 달라지더라도 두 값의 차가 같다면 경로의 개수는 일치한다.

 

만일 h = 0, n = 3이라고 한다면

0 0 n

0 0 0

h 0 0 

이러한 형태로 위치한다.

x < y 인 지역은 침수되어 지나갈 수 없으므로

 

0 0 1

0 1 1

1 1 1 

1로 표시된 부분만 지나갈 수 있다.

따라서 모든 경로의 수를 세기 위해서 각 좌표를 지나갈 때마다 표시를 한다면 그 도착 점에 적힌 숫자가 정답이 된다.

 

0 0 0

0 1 +

1 1 1

+로 표시된 부분을 갈 수 있는 방법은 플러스 왼쪽에서 가거나 아래쪽에서 갈 수 있다.

(상하좌우 모두로 움직일 수 있지만 최단 경로로 가기 위해서는 '오른쪽, 위쪽' 혹은 '왼쪽, 아래쪽'으로만 갈 수 있기 때문)

 

따라서 +의 값은 왼쪽의 값인 1과 아래쪽의 값인 1을 더해 2가 된다.

이런 식으로 모든 경우를 채워주면 된다.

하지만 리스트에 채울 때는 

0번째부터 채우는 것이 편하기에 

h 0 0

0 0 0

0 0 n 

형태로 가정하고 코드를 작성한다.(두 값의 차만 중요하기 때문)

import sys
input = sys.stdin.readline


h, n = map(int, input().split())

diff = abs(h - n) + 1

arr = [[0 for _ in range(diff)] for i in range(diff)]

for i in range(diff):
    arr[0][i] = 1


for i in range(1, diff):
    for j in range(i, diff):
        arr[i][j] = arr[i-1][j] + arr[i][j-1]

print(arr[-1][-1])