[Python] 백준 20152 Game Addiction

문제
강산이는 심각한 게임 중독자이기 때문에 날씨에 상관없이 매일 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방까지 갈 수 있는 경로의 개수를 출력한다.

예제 입력 1
8 4
예제 출력 1
14

예제 입력 2
0 3
예제 출력 2
5

코드

# 20152 Game Addiction

H, W = map(int, input().split())

start = 0
end = abs(H - W) + 1

numbers = [[0] * end for _ in range(end)]
for i in range(end):
    numbers[0][i] = 1

for i in range(1, end):
    for j in range(i, end):
        numbers[i][j] = numbers[i - 1][j] + numbers[i][j - 1]

ans = numbers[-1][-1]
print(ans)

(코드에서 start = 0은 안 써도 됐다..)

해설

좌표 값을 구할 때, H와 W값이 무엇인지는 중요하지 않다.
H, W가 얼마나 차이나는지가 중요하다.
H = 0, W = 5일 때와
H = 5, W = 10일 때의 결과는 같기 때문이다.
H = 10, W = 5일 때의 결과도 마찬가지로 같다.

경우의 수를 따질 때, 문제대로라면 왼쪽 위에서 오른쪽 아래로 대각선을 그었을 때, 위쪽 부분이 침수되었지만,
경우의 수를 구할 때에 아래쪽 부분이 침수된 것으로 생각해도 무방하다. 편의를 위해 아래쪽이 침수된 것으로 생각했다.

0, 0에서 3, 3으로 갈 때, 경우의 수를 모든 칸에 기록하면서 이동하면 다음과 같다.

1 1 1 1
0 1 2 3
0 0 2 5
0 0 0 5

8, 8에서 4, 4로 갈 때의 경우의 수는, 0, 0에서 4, 4로 갈 때의 경우의 수와 동일하다.
0, 0에서 4, 4로 갈 때, 경우의 수를 마찬가지로 모두 기록해보면

1 1 1 1 1
0 1 2 3 4
0 0 2 5 9
0 0 0 5 14

와 같은 결과를 얻을 수 있다.

눈치 빠른 독자는 벌써 눈치를 챘을 것 같다.

내가 푼 방식은 다음과 같다.

1. H, W의 차이를 구한다.
2. N = abs(H - W) + 1
3. N*N 배열을 만들고 0으로 초기화한다.
4. 첫 행에 1을 집어넣는다.
5. [1, 1]에서부터, 위와 왼쪽 값을 더한 결과를 대입해준다.

손쉽게 모든 경우의 수를 구할 수 있음을 알 수 있다.