[제주코딩베이스캠프] 눈떠보니 코딩테스트 전날 | 문제7. Eureka!

---

---

1. matrix 형태의 동적 계획법
- Recursion
-memorization

이동 방법 1. 맨 왼쪽에서 시작할 경우
이동할 수 있는 방향 : 오른쪽, 아래

3으로 이동하는 최단 거리를 구하는 방식
> min(최소경로(i-1,j), 최소경로(i,j-1)+값(i,j)

일반적으로는 왼쪽에서 출발해서 오른쪽으로 순회를 한다.

하지만 문제에서는 다르다.
오른쪽에서 출발해서 왼쪽으로 순회한다.

---

cross=[ [[3, 0, 1, 1, 8], [5, 0, 4, 5, 4], [1, 5, 0, 5, 1], [1, 2, 1, 0, 1], [0, 2, 5, 1, 1]], [[1, 2, 0, 3, 3], [1, 2, 0, 2, 4], [1, 2, 0, 2, 4], [4, 2, 0, 0, 1], [8, 4, 1, 1, 0]], ] cross_=cross[0]+cross[1] #cross_ ''' cross_= [[3, 0, 1, 1, 8], [5, 0, 4, 5, 4], [1, 5, 0, 5, 1], [1, 2, 1, 0, 1], [0, 2, 5, 1, 1], [1, 2, 0, 3, 3], [1, 2, 0, 2, 4], [1, 2, 0, 2, 4], [4, 2, 0, 0, 1], [8, 4, 1, 1, 0]] ''' for i in range(len(cross_)): for j in range(4,-1,-1): print(i,j,cross_[i][j]

c =[[3, 0, 1, 1, 8], [5, 0, 4, 5, 4], [1, 5, 0, 5, 1], [1, 2, 1, 0, 1], [0, 2, 5, 1, 1], [1, 2, 0, 3, 3], [1, 2, 0, 2, 4], [1, 2, 0, 2, 4], [4, 2, 0, 0, 1], [8, 4, 1, 1, 0]] 가중치누적값 = [[0 for i in range(5)] for j in range(len(c))] 좌표저장 = [[[0, 0] for i in range(5)] for j in range(len(c))] for i in range(len(c)): for j in range(4, -1, -1): if i == 0 and j == 4: 가중치누적값[0][4] = c[0][4] 좌표저장[i][j] = [99, 99] # 종료점을 찾기 위한 작업 elif i == 0: 가중치누적값[i][j] = 가중치누적값[i][j + 1] + c[i][j] 좌표저장[i][j] = [i, j + 1] elif j == 4: 가중치누적값[i][j] = 가중치누적값[i - 1][j] + c[i][j] 좌표저장[i][j] = [i - 1, j] else: # 가중치누적값[i][j]=min(가중치누적값[i][j-1],가중치누적값[i-1][j])+c[i][j] if 가중치누적값[i][j + 1] > 가중치누적값[i - 1][j]: 가중치누적값[i][j] = 가중치누적값[i - 1][j] + c[i][j] 좌표저장[i][j] = [i - 1, j] else: 가중치누적값[i][j] = 가중치누적값[i][j + 1] + c[i][j] 좌표저장[i][j] = [i, j + 1] print(좌표저장) # 경로 찾는 방법 k = 0 while True: if k == 0: i, j = 좌표저장[len(c) - 1][0] else: i, j = 좌표저장[i][j] if i == 99 and j == 99: break k += 1 print(i,j)

x=[[[None] * 3] * 3 ] * 2 x[0][0][0]=1000 print(x)

# x[0][0][0]의 주소값을 공유하고 있어서, x[0][1][0], x[0][2][0], x[1][0][0],x[1][1][0],x[1][2][0]의
값이 모두 0으로 바뀐다. 따라서 for을 이용하여 초기화해줘야 한다.