1890 점프

1. 문제

문제는 링크에 들어가면 있다.

2. 정답 코드

문제의 내 정답 코드는 다음과 같다.

import sys
read = sys.stdin.readline

N = int(read())
graph = []
for _ in range(N):
    graph.append(list(map(int,read().split())))

# 우, 하
dr = [1,0]
dc = [0,1]

"""
그래프를 전부 탐색하면서 우,하에 갈 수 있는 곳에 +1을 해주면 된다.
"""
dp_table = [[0 for _ in range(N)] for _ in range(N)]
dp_table[0][0] = 1
for c in range(N):
    for r in range(N):
        if c == N-1 and r == N-1 :
            continue
        now = graph[c][r]
        for i in range(2):
            nr = r + dr[i] * now
            nc = c + dc[i] * now

            if 0<= nr < N and 0 <= nc < N and dp_table[c][r] != 0:
                dp_table[nc][nr] += dp_table[c][r]
# for j in range(N):
#     print(dp_table[j])
print(dp_table[-1][-1])

사실 DFS로 먼저 풀었었는데 시간초과가 됬었다. 그러나 기록을 위해 남겨둔다.

import sys
read = sys.stdin.readline

N = int(read())
graph = []
for _ in range(N):
    graph.append(list(map(int,read().split())))

# 우, 하
dr = [1,0]
dc = [0,1]

def dfs(r,c):
    # 먼저 현재 위치가 벽을 넘었는지부터 보자
    if r<0 or r>=N or c<0 or c>=N :
        return 0

    # 현재 위치가 벽을 넘지 않았으면 여기부터 실행
    # 종착점에 했으면 return 1하고 dfs끝
    if graph[c][r] == 0 :
        return 1
    else :
        # 그렇지 않다면 아래,오른쪽을 dfs로 탐색할 것.
        temp = 0
        for i in range(2):
            nr = r+dr[i]*graph[c][r]
            nc = c+dc[i]*graph[c][r]
            temp += dfs(nr,nc)
        return temp
print(dfs(0,0))

3. 풀이 및 생각

문제 풀이

이 문제는 2중 for문을 사용해서 하나씩 훑어가면서 풀어야 한다. 왜냐하면 각 칸에 따라 갈 수 있는 칸이 정해져 있기 때문이다. 음.. dp문제이기 때문에 점화식을 세워본다면 $ d[c][r]\;=\; d[c-위에서 올 수 있는][r] + d[c][r-왼쪽에서 올 수 있는]$ 이런 느낌이다.

나의 생각

전에 본 적이 있을지도 모르지만.. 이런 유형의 dp는 익숙치 않음에도 뭔가 딱 생각이 난게 신기하다!! 점점 발전하고 있다는 의미일까??