레벨02만 푸는데 아무래도 레벨02는 너무 쉬운 거 같아 제자리 걸음하는 느낌이라 레벨03의 문제도 하루에 1~2문제는 풀어야겠다고 생각함
문제 요약
꼭대기에서 내려가는데, 내려갈 때는 인접한 가지로만 내려갈 수 있고 내려가면서 누적 합을 구하는데 끝까지 내려갔을 때 가장 큰 누적 합을 구하고자 한다.
이거 솔직히 못 풀어서 공부하자는 느낌으로 공부 했다.
재귀로 풀어야 하나라고 생각했지만 전혀 생각나지 않아서 뇌정지가 왔다 ㅋㅋ..
DP (Dynamic Programming)으로 푸는 문제인데... 사실 DP랑 재귀의 차이점이 뭔지 몰라서 좀 찾아 봤다
- DP : 앞의 값들을 이용해서 다음 값을 구하는 것. A[n] = A[n-1] + A[n-2] 이런 느낌인 듯 싶다... 아니 학교에서 안 알려줬음 ;;
- 재귀 : 특정 조건까지 깊게 들어가서 값을 가져오는 ..?
코린이기 때문에 아직 느낌만 알고 이렇게 텍스트로 작성하려니까 잘 안된다 ;;
정답코드(1)
- 아래서 위로 올라가기
def solution(triangle):
floor = len(triangle)-1
while floor>0:
for i in range(floor):
triangle[floor-1][i] += max(triangle[floor][i], triangle[floor][i+1])
floor -= 1
return triangle[0][0]아래 줄의 두개를 비교해서 큰 값을 아래 줄의 작은 인덱스 값에 누적하여 더하는 것이다.
쉽게 말해서 0,1번째 인덱스 값을 비교했을 때, 무조건 윗줄 0번째 인덱스에 큰 값을 누적 시킨다는 것이다.
그래서 아래에서 올라가게 되면 젤 위에는 항상 제일 큰 값이 저장되게 된다!!
근데 이건 내가 푼 게 아니라 이해하여 베낀 풀이라서 ...
스스로 위에서 아래로 내려오는 코드는 내가 짜봤다.
정답코드(2)
def solution(tri) :
for row in range(1, len(tri)):
for col in range(0, len(tri[row])):
if col == 0 :
tri[row][col] += tri[row-1][0]
elif col == len(tri[row])-1 :
tri[row][col] += tri[row-1][len(tri[row-1])-1]
else :
tri[row][col] += max(tri[row-1][col-1], tri[row-1][col])
flr = len(tri)-1
return max(tri[flr])외부 row는 층을, 내부 col은 열을 나타낸다.
맨 위 0층은 위에서 더해지는 게 아니니까 층을 나타내는건 1부터 len(tri)-1까지 반복한다.
열을 나타내는 건 정상적으로 0부터 len(tri[row])-1까지 반복한다.
여기서 추가로 끝에 있는 열일 때와 중간에 있는 열일 때의 차이를 보게 되면, 끝은 바로 바로 위에 있는 거 하나만 조건 없이 더해지지만 중간은 두개 중 큰 것과 더해진다. 그래서 max를 통해서 tri[row-1][col-1], tri[row-1][col] 중 큰 값이 tri[row][col]에 더해지게 된다.
그래서 결국 마지막 층의 가장 큰 값을 반환하면 된다!
ㅇㅏ 좀 어렵네 ;;; 앞으로 꾸준히 레벨03 근육 좀 키우자
