[백준 1932] DP 동적계획법3

드디어! 혼자 힘으로 푼 문제. 사실 전의 문제 [백준 1149]에서 조금 변형된 수준이라 풀 수 있었다.

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

for i in range(1,n):
    t[i][0] = t[i][0] + t[i-1][0]
    t[i][i] = t[i][i] + t[i-1][i-1]
    for j in range(1,i):
        t[i][j] += max(t[i-1][j-1],t[i-1][j])
        
print(max(t[n-1]))

지금까지 풀었던 dp 문제들은 dp 변수에 리스트를 지정해줬기 때문에 이 문제도 그렇게 풀기 시작했다.

dp = [[0]*(i+1) for i in range(n)] 으로 놓고 풀다가 보니 입력받은 값이랑 똑같이 설정하게 됐다.

그래서 dp 변수를 빼고 입력받은 리스트를 변형해가는 방식으로 풀었다.

 

간단히 설명하자면, 바로 위층의 두 값 중 더 큰 것을 선택해서 현재 값에 바로바로 더해가는 것이다.

그렇게 하면 마지막 층인 n층의 각 n개의 값에 더 큰 것들을 더해나간 최종 값이 나온다. 그 중에서도 가장 큰 것을 출력한다.

 

우선 삼각형의 왼쪽과 오른쪽 변, 즉 각 층의 리스트 양끝은 선택지가 위층의 양끝밖에 없다.

예를 들어 3층의 0번째 값은 바로 위의 값인 2층의 0번째 값밖에 선택하지 못하고, 4층의 3번째 값 또한 3층의 2번째 끝값만 선택할 수 있다.

1. 따라서 선택지가 없는 각 층의 양끝 값들은 현재 값에 그대로 바로 위의 값을 더해놓는다. (line 7~8)

2. 설정된 양끝값을 제외하고 각 층의 나머지 값들은 위층에서 선택할 수 있는 대각선 왼쪽, 오른쪽 값 중 더 큰 값을 더한다. (line 10)

3. 이렇게 모든 층을 반복하면 처음 입력받은 값의 마지막 층(리스트) 값들이 최종적으로 더한 값이 된다. (line 9)

4. 최종값이 들어있는 마지막 리스트 t[n-1] 의 최대값을 print하면 된다.