알고스팟 외발 뛰기(jumpgame) 문제 파이썬으로 풀기

숫자 격자를 입력받아서, 맨 처음 칸부터 맨 마지막 칸까지 갈 수 있나를 알아보는 문제이다.

전형적인 동적계획법 문제이다. 만약 동적계획법을 아주 잘 알고 있다면, 이 문제는 매우 쉽게 느껴졌을 것이다. 하지만 나는 동적계획법 문제를 볼때마다 머리가 아파지는 초보 코더이기 때문에, 여러번의 삽질을 겪었다.

 

#jumpgame
def jump(numlist, x, y):  # 숫자 격자와 현재 x, y 위치를 입력받음
    if x >= n: return False  # x축 칸을 넘어간 경우
    if y >= n: return False  # y축 칸을 넘어간 경우
    if x == n-1 and y == n-1:  # 마지막 칸에 도달
        return True
    result = record[x][y]  # 메모이제이션
    if result != -1: return result  # 이미 계산했다면
    move = numlist[x][y]  # 현재 위치의 칸에 쓰여있는 숫자
    result = max(result, jump(numlist, x+move, y))  # x축 이동
    result = max(result, jump(numlist, x, y+move))  # y축 이동
    record[x][y] = result  # 현재 위치 저장
    return result
 
 
case = int(input())
for i in range(case):
    n = int(input())
    numlist = []
    record = [[-1 for k in range(n)] for l in range(n)]  # 메모이제이션을 위한 리스트
    for j in range(n):
        numlist.append(list(map(int, input().split())))
    if jump(numlist, 0, 0):
        print("YES")
    else:
        print("NO")

경험이라고 치기도 애매하지만, 지금까지 동적계획법을 이용해 문제를 풀 때의 경험에서 가장 중요한 것은 값을 저장하는 것과 앞으로의 진향을 위한 점화식을 세우는 것이라고 느꼈다.

값을 저장하는 것은 나름 쉽게 구현이 가능하다. 파이썬의 경우는 그저 리스트를 하나 생성하고 거기에 값을 넣는다 라고만 하면 되니까. 하지만 점화식은.. 문제를 풀때마다 이렇게 하는게 맞나 라는 생각이 들때가 매우 많다. 이번에도 그랬는데, result=max(result,jump())를 할때 max를 쓰는게 직감적으로는 맞아 보여서 썼으나, 실제 머리로는 왜 max를 써야 정답이 나오는지 아직도 이해가 되지 않는다. 도대체 왜 max를 써야 하는 것인가?

아무튼 정답이 나오긴 했다.

 

느낀점:

1. 동적계획법 말고도 어려운 알고리즘이 너무 많다. 빠르게 정리해야 할듯.

2. 이번 문제를 풀 때

https://blog.naver.com/kks227/220777103650

이 글의 도움을 매우 많이 받았다. 밑에 보면 동적계획법 연습용 문제도 추천해주는 등 좋은 글이다. 즐겨찾기 해놓고 나중에 읽어보면 코딩 실력을 확실히 높일 수 있을 거 같다.