반응형

문제

행의 수가 N이고 열의 수가 M인 격자의 각 칸에 1부터 N×M까지의 번호가 첫 행부터 시작하여 차례로 부여되어 있다. 격자의 어떤 칸은 ○ 표시가 되어 있다. (단, 1번 칸과 N × M번 칸은 ○ 표시가 되어 있지 않다. 또한, ○ 표시가 되어 있는 칸은 최대 한 개이다. 즉, ○ 표시가 된 칸이 없을 수도 있다.)

행의 수가 3이고 열의 수가 5인 격자에서 각 칸에 번호가 1부터 차례대로 부여된 예가 아래에 있다. 이 격자에서는 8번 칸에 ○ 표시가 되어 있다.

img

격자의 1번 칸에서 출발한 어떤 로봇이 아래의 두 조건을 만족하면서 N×M번 칸으로 가고자 한다.

  • 조건 1: 로봇은 한 번에 오른쪽에 인접한 칸 또는 아래에 인접한 칸으로만 이동할 수 있다. (즉, 대각선 방향으로는 이동할 수 없다.)
  • 조건 2: 격자에 ○로 표시된 칸이 있는 경우엔 로봇은 그 칸을 반드시 지나가야 한다.

위에서 보인 것과 같은 격자가 주어질 때, 로봇이 이동할 수 있는 서로 다른 경로의 두 가지 예가 아래에 있다.

  • 1 → 2 → 3 → 8 → 9 → 10 → 15
  • 1 → 2 → 3 → 8 → 13 → 14 → 15

격자에 관한 정보가 주어질 때 로봇이 앞에서 설명한 두 조건을 만족하면서 이동할 수 있는 서로 다른 경로가 총 몇 개나 되는지 찾는 프로그램을 작성하라.

입력

입력의 첫째 줄에는 격자의 행의 수와 열의 수를 나타내는 두 정수 N과 M(1 ≤ N, M ≤ 15), 그리고 ○로 표시된 칸의 번호를 나타내는 정수 K(K=0 또는 1 < K < N×M)가 차례로 주어지며, 각 값은 공백으로 구분된다. K의 값이 0인 경우도 있는데, 이는 ○로 표시된 칸이 없음을 의미한다. N과 M이 동시에 1인 경우는 없다.

출력

주어진 격자의 정보를 이용하여 설명한 조건을 만족하는 서로 다른 경로의 수를 계산하여 출력해야 한다.

예제 입력 1

3 5 8

예제 출력 1

9

나의 풀이

이 문제는 주어지는 지도에서 동그라미가 쳐지는 곳을 잘 찾아서 지도를 나눈다음 두 개에서 나오는 경로를 곱해주면 되는 문제이다. 우선 k가 0이라는 말은 아무곳도 거치지 않는 다는 뜻으로 (1,1)에서 (n,m)으로 가는 경로의 수를 구하면 된다.

IMG_5D99AA1AB802-1

그렇지않으면 위에서 처럼 매겨지는 번호의 인덱스 값을 찾아내서 지도를 나누어야한다. 이 문제에서 핵심은 저거였다고 생각한다. k에 따라서 인덱스를 구하는 식을 일반화 시키면 아래와 같다.

# 왼쪽 위 지도
dotN1 = (k-1) // m + 1
dotM1 = k - (dotN1-1) * m

# 오른쪽 아래 지도
dotN2 = n - (dotN1-1)
dotM2 = m - (dotM1-1)

그럼 이제 중간 지점이 설정되었다. 그럼 dotN1,dotM2로 dp를 하나 만들고 dotN2,dotM2 로 또 다른 dp를 만들어 각각의 dp에서 '(1,1)에서 (n,m)까지 가는 경로의 수를 구해 서로 곱해주면 전체 경우의 수가 나온다.'

위에서 전체 경로의 수를 구해내는 방법을 살펴봤다면 이제 각 dp에서 경로의 수를 구하는 법을 보겠다. 이 문제는 인접한 오른쪽과 아래로만 움직일 수 있다고 한다. 그럼 현재의 위치에서 가능한 경로의 수는 위에서의 경로의 수와 왼쪽에서 경로의 수를 더해주면 된다. 식으로 쓰면 dp[i][j] = dp[i-1][j] + dp[i][j-1]이 된다.

IMG_7D4952652B7C-1

코드

# 10164번 격자상의 경로
import sys

# 경로 수 구하는 함수
def find(y,x):
    dp = [[0 for _ in range(x+1)] for _ in range(y+1)]

    for i in range(1,y+1):
        for j in range(1,x+1):
            if i == 1 and j == 1:
                dp[i][j] = 1
                continue

            dp[i][j] = dp[i-1][j] + dp[i][j-1]

    return dp[y][x]

# main
n, m, k = [int(x) for x in sys.stdin.readline().split()]

if k == 0:      # 중간지점이 없는 경우
    print(find(n,m))

else:       # 중간지점이 있는 경우
    dotN1 = (k-1) // m + 1
    dotM1 = k - (dotN1-1) * m
    dotN2 = n - (dotN1-1)
    dotM2 = m - (dotM1-1)

    # 왼쪽 위 경로
    r1 = find(dotN1,dotM1)
    # 오른쪽 아래 경로
    r2 = find(dotN2,dotM2)

    print(r1*r2)
반응형

BELATED ARTICLES

more