삼각형 위의 최대 경로
6
1 2
3 7 4
9 4 1 7
2 7 5 9 4
1
2 4
8 16 8
32 64 32 64
128 256 128 256 128맨 위의 숫자에서 부터 한 번에 한 칸씩 아래로 내려가 맨 아래 줄까지 닿는 경로를 만들려 함.
경로는 바로 아래 혹은 오른쪽 아래로 내려갈 수 있다.
숫자의 합을 최대화하는 경로는 무엇이고, 최대 합은 얼마일까?
접근.
새로운 2차원 리스트를 만들어 max() 값을 업데이트 하자.
각 지점에서 확인 할 값들은. [-1][0] or [-1][1]의 값이다.
코드.
cache = [[-1] * 101 for _ in range(101)]
def route(x, y):
dx = [1, 1]
dy = [0, 1]
for i in range(2):
nx = x + dx[i]
ny = y + dy[i]
cache[nx][ny] = max(cache[nx][ny], graph[x][y] + graph[nx][ny])이렇게 하면 되지 않을까???
해답.
현재 위치, 합
pathSum(y, x, sum)
아래 쪽으로, 오른쪽으로 내려 갔을 때의 최대 합.
path1(y, x, sum) = max(path(y + 1, x, sum + triangle[y][x]), path(y + 1, x + 1, sum + triangle[y][x]))
무식하게 메모이제이션.
cache = [[-1] * 101 for _ in range(101)]
triangle = [[[-1] * 101 for _ in range(101)]]
n = 높이.
def path1(y, x, sum):
if y == n - 1:
return sum = triangle[y][x]
ret = cache[y][x][sum]
if ret != -1:
return ret
sum += triangle[y][x]
return ret = max(path1(y + 1, x + 1, sum), path1(y + 1, x, sum))점화식 대로 만드니 cache의 메모리가 너무 크다....
입력을 걸러내자.
- y와 x의 경우 부분 문제를 지정한다.
- sum의 경우 지금까지 푼 문제에 대한 정보를 주는 것.
이미 푼 문제에 대한 정보는 다음 부분 문제를 해결하는 것에는 아무 상관이 없다.
sum을 제외하자.
그러면 어떻게 최대 경로를 반환 하는 가????
-> 부분 경로들의 최대치를 반환하게 하자.
path2(y, x) = triangle[y][x] + max(path2(y + 1, x), path2(y + 1, x + 1))
cache = [[-1] * 101 for _ in range(101)]
triangle = [[[-1] * 101 for _ in range(101)]]
n = 높이.
def path1(y, x, sum):
if y == n - 1:
return triangle[y][x]
ret = cache[y][x]
if ret != -1:
return ret
return ret = triangle[y][x] + max(path1(y + 1, x + 1), path1(y + 1, x))점화식 생각하는게 개 레전드네......
triangle 변수의 값을 변화시키기 때문에 마지막에는 삼각형 변수를 출력해준다.
