전공/프로그래머스
정수 삼각형
yha97
2023. 10. 3. 20:43
날짜 : 2023. 10. 03
사용 언어 : python
문제
코드
def solution(tri):
r = len(tri)
res = [[0] * i for i in range(1, len(tri) + 1)]
res[0] = tri[0]
for i in range(len(tri)-1):
for j in range(i + 1):
now = res[i][j]
left = tri[i+1][j] # 왼쪽 아래의 수
res[i+1][j] = max(now + left, res[i+1][j])
right = tri[i+1][j+1] # 오른쪽 아래의 수
res[i+1][j+1] = max(now + right, res[i+1][j+1])
# for i in res:
# print(i)
return max(res[-1])
풀이
- 전형적인 DP 문제이다.
- 위 그림과 같이 임의의 점 (i, j)의 케이스에서는 각각 왼쪽으로는 (i+1, j)가 해당되고, 오른쪽으로는 (i+1, j+1)이 해당된다.
- 각각의 row별로 max값을 갱신해야 하기 때문에 미리 값들을 0으로 초기화하여 max() 함수를 사용해 최신화하기 쉽게 설정한다.
- 그 다음 2중 for문을 사용해서 갱신해 나가고, 마지막에는 가장 아래의 row에서 최대값을 리턴하는 방식으로 답을 출력하면 된다.
알게된 점
- 값들을 갱신하지 않고 임의의 리스트 tmp를 만들어서 각 row별로 넣는 방식으로 문제를 풀었다.
- 케이스가 하나였고 그 케이스는 바로 맞아서 제출했지만 오답이 나왔고, 그덕에 틀렸던 부분을 찾을 수 있었다.
- 만약 실제 코딩테스트였다면 틀린 채 넘어갔을 수 있기 때문에 한번에 맞힐 수 있도록 노력해야겠다.
참고 사이트
-