이것이 코딩테스트다 32 정수 삼각형

문제 링크

https://www.acmicpc.net/problem/1932

1932번: 정수 삼각형

---

Test Case

---

문제 풀이

우선 입력은  줄구분 할필요 없이 그냥 list 한줄씩 입력을 받으면 된다. 그리고 for문을 통해서 각 케이스를 나눈 뒤, index 값을 고려해서 반복문을 만들어준다 i 의 범위 1~n, j 의 범위 0~i+1 인것은 각 인덱스의 최소,최대값을 생각하면 쉽게 범위를 잡을 수 있다.
마지막으로 정답 출력은 마지막줄에서 제일 큰 dp 배열의 값이 되므로 dp[n-1]의 값을 출력하면 된다.

여태까지 알고리즘 공부하고 풀이하던 방식을 조금 바꿔야겠다.
기존에는 정답으로 가는 과정만 기록했었는데, 그게 아니라 문제풀면서 어떤 에러들이 나왔는지, 왜그런 에러가 발생했는지, 어떻게 해결했는지 등도 같이 기록할 예정이다. 문제풀이를 너무 날먹으로 했고, 스터디를 하다보니 남들에게 설명했을 때 이해를 돕기 위해서 출력문이랑 에러떴을때 어떻게 수정했는지의 정리도 필요 할 것 같다. 내가 다른 사람에게 설명을 너무 못한다는 생각이 스터디하면서 들었는데 개선해봐야겠다. 

---

Source Code

import sys
input = sys.stdin.readline

n = int(input())
dp = []
for _ in range(n):
    dp.append(list(map(int, input().split())))

# for i in range(n):
#     print(dp[i])

for i in range(1,n):
    for j in range(i+1):
        # 제일 왼쪽
        if j == 0:
            dp[i][j] += dp[i-1][j]
        # 제일 오른쪽
        elif j == i:
            dp[i][j] += dp[i-1][j-1]
        # 나머지 가운데
        else :
            dp[i][j] = max(dp[i][j]+ dp[i-1][j], dp[i][j] + dp[i-1][j-1])

# for i in range(n):
#     print(dp[i])

print(max(dp[n-1]))