[PY] 1890 : 점프

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

아 대체 이걸 어떻게 만들었는지 까먹었다.

1. 0,0 으로 시작해서 n, n에서 끝난다고 언급되어있다. 그럼 모든 길은 0,0이 필요한 거니까, 우선 0,0에서 도달 가능한 곳들에 기록을 남긴다.
2. 기록이 남았다는 것은 경로가 될 조건인 0,0 경유를 달성한 것이다. 따라서, 전체 순회를 돌리는 와중에 이렇게 기록이 있는 애들만 위주로 시도하면 된다. 그리고 전체 순회도 그냥 반복문 두개를 중첩해서 쓰면 되는게, 전제 조건중 우측과 아래쪽으로만 점프를 시도 할 수 있다는 점에서 착안 할 수 있었다.
3. 다만 여기서 막히는 부분을 생각 할 수 있는게, 결과적으로 결승선에는 모든 해결 가능한 기법들의 갯수가 누적되어야한다. 대표 테스트 케이스만 보면 각기 오는길이 다르겠거니 하면서 += 1을 했지만 2에서 오면 방법은 2가지가 늘어나는거다. 그래서 방법이 더 많은 선택지일 수 있다는 것을 상기하니 코드가 그 부분을 반영 할 수 있도록 해야 했다.

정답!

# 무슨말인지는 알겠는데, 이걸 어떻게 dp로 하는거지?
import sys
input = sys.stdin.readline

fieldSize = int(input())
field = [[0 for _ in range(fieldSize)] for _ in range(fieldSize)]
dp = [[0 for _ in range(fieldSize)] for _ in range(fieldSize)]

for i in range(fieldSize):
    numList = list(map(int, input().split()))[:fieldSize]
    field[i] = numList

# 초기값을 0, 0에서 출발하도록 한다.
firstJumpCnt = field[0][0]

if(firstJumpCnt < fieldSize):
    dp[firstJumpCnt][0] += 1
    dp[0][firstJumpCnt] += 1

for i in range(fieldSize):
    for j in range(fieldSize):
        if(dp[i][j] > 0 and field[i][j] != 0):
            # 얘는 최종 점에 도달 할 수도 있는 상태라서 유망한 애들을 대상으로 확인 할 것이다.
            if (i + field[i][j]) < fieldSize:
                # 아래를 향한 데이터 추가가 유효한 범위 인지 확인한다.
                    #print(f" 아래 향함, {i+field[i][j]}, {j}에 데이터 추가 시도")
                    #print(f"이 데이터는 {i}, {j}에서 시작되었음!")
                    if(dp[i + field[i][j]][j] == 0):
                        dp[i + field[i][j]][j] = dp[i][j]
                    else: 
                        dp[i + field[i][j]][j] += dp[i][j]

            if (j + field[i][j]) < fieldSize:
                # 우측을 향한 데이터 추가가 유효한 범위 인지 확인한다.
                    #print(f"우측 향함, {i}, {field[i][j] + j}에 데이터 추가 시도")
                    #print(f"이 데이터는 {i}, {j}에서 시작되었음!")
                if(dp[i][j + field[i][j]] == 0):
                    dp[i][j + field[i][j]] = dp[i][j]
                else:
                    dp[i][j + field[i][j]] += dp[i][j]
            
            #print("Status!")
            #print(f"progress {i} {j}")

            #for k in range(fieldSize):
                  #print(dp[k])
                 
            #print("-----")

print(dp[fieldSize - 1][fieldSize - 1])