#1932 정수 삼각형

💯 문제 → 삼각형이 주어지는데 맨 위에서 부터 아래에 있는 수 중 하나를 선택하여 아래층으로 내려올 때, 이제까지 선택된 수의 합의 최대를 구하는 문제 ! 트리 생각하면 될듯 !

<💭 방법>

🎈 1 동적계획법 .. ?

• 모든 경우의 수를 전부다 생각하는 방식으로 진행한다.
• 입력을 리스트로 받고 각 행의 0번째 열같은 경우에는 바로 전 행의 0번째 원소의 값을 이용하는 경우 밖에 없으므로 두개의 값을 더해 리스트의 원소의 값을 교체한다.
• 각 행의 마지막 여로 마찬가지로 전 행의 마지막 열 밖에 경우의 수가 없으니 각 원소를 더해 원소의 값을 교체한다.
• 위 두개의 경우 빼고 나머지 리스트의 원소의 값은 바로 전 행의 같은 열과 다음 열의 값을 비교하여 더 큰 수를 선택해 그 수와 더한 값을 교체하는 방식으로 진행한다.

<🥰 첫번째 코드>

triangle[1][0] = triangle[0][0] + triangle[1][0]
triangle[1][1] = triangle[0][0] + triangle[1][1]

for i in range(2, N):
    triangle[i][0] = triangle[i-1][0] + triangle[i][0]
    for j in range(1, i+1) :
        if j == i:
            triangle[i][j] = triangle[i-1][j-1] + triangle[i][j]
        else:
            triangle[i][j] = max(triangle[i-1][j-1], triangle[i-1][j]) + triangle[i][j]

<느낀점>
생각보다 엄청 빨리 풀어서 당황했던 문제 .. 근데 알고리즘 생각하는게 어려움 ㅜㅜ .. 규칙 찾기는 왜 어려운걸까 ㅎ .. 동적계획법을 사용하여 풀고 싶었는데 .. 과연 동적계획법을 사용한게 맞는지 의문이 가는 문제 .. 사용한게 아니라면 어떻게 사용하는게 좋을지 알려주세여 다들 ..