Jumpgame.py

동적계획법을 공부하면서 나오는 예시 문제였다.
동적계획법은 분할정복에서 계속 풀이 방식이 바뀌는 것이라고 한다.
그래서 cache를 넣어서 푸는 방법이 가장 적합하다고 한다.
이 문제는 다음 사이트에 있다.
https://www.algospot.com/judge/problem/read/JUMPGAME

개인적으로 문제를 해결하지 못하여 다음 블로그에서 가져와서 쓰기로 했다
https://doctcoder.tistory.com/30

def jump(board, x, y):
	if x >= n or y >= n: return False
    if x == n-1 and y == n-1:
    	return True
    result = cache[x][y]
    if result != -1: return result
    move = board[x][y]
    result = max(result, jump(board, x+move, y))
    result = max(result, jump(board, x, y+move))
    cache[x][y] = result
    return result
    
case = int(input())
for i in range(case):
	n = int(input())
    board = []
    cache = [[-1] * n for j in range(n)]
    for k in range):
    	board.appen(list(map(int, input().split())))
    if jump(board, 0, 0):
    	print('yes')
    else:
    	print('no')

잘 이해가 안가는 부분은 다음과 같다.

max(result, jump(board, x+move, y))

그래서 한번 실험을 해보기로 했다.

print(max(True,True))
print(max(True, False))
print(max(False, False))
print()

print(max (1, True))
print(max (1, False))
print(max (0, True))
print(max (0, False))
print(max (-1, True))
print(max (-1, False))
print()

print(max (True, 1))
print(max (True, 0))
print(max (False, 1))
print(max (False, 0))
print(max(True, -1))
print(max(False, -1))

위에 코드를 실행 시키면 다음과 같이 결과가 나온다.

True
True
False

1
1
True
0
True
False

True
True
1
False
True
False

대충 예상을 해보자면, 1 > True > 0 > Fasle > -1~ 인것 같다.
참고로 위 실험 환경은 3.8.2버전이다.

즉 cache를 -1 로 초기화 했으므로, False값이라고 생각 할 수 있는 것이다.

---

Summery.

1. 동적계획법은 Cache를 이용한 분할정복이다.
2. python에서 max로 비교할때, 1 > True > 0 > False > -1 이라고 생각하면 좀더 편하게 할 수 있다.