[백준 1932] 정수 삼각형

1. 문제

www.acmicpc.net/problem/1932

1932번: 정수 삼각형

2. 접근 방법

dp문제다.

 

삼각형이 아니라 2차 배열로 생각해보면 

 

input의 경우

 

0

0 0

0 0 0

0 0 0 0

 

이런 형상이다.

 

그럼 얘를 좌표로 나타내면 ([열(x), 행(y)]으로 나타냈습니다.)

 

           [0, 0]

       [0, 1] [1, 1]

    [0, 2] [1, 2] [2, 2]

[0, 3] [1, 3] [2, 3] [3, 3]

 

[0, 1]까지의 합은 [0, 0]과 [0, 1]을 더한 값

[1, 2]까지의 합은 [0, 1]과 [1, 1] 둘 중 더 큰 값과 [1, 2]를 더한 값

...

이렇게 하는 것을 알 수 있다.

 

따라서 [x, y]까지의 합은 max([x-1, y-1], [x, y-1]) + [x, y] 로 나타낼 수 있다.

 

이 때 합을 저장해주는 행렬을 N*N 행렬로 만들고 빈 값을 모두 0으로 채워주면, 오른쪽 영역은 신경쓰지 않아도 된다.

 

3. 코드

python

N = int(input())
board = [list(map(int, input().split())) for _ in range(N)]

ans = [[0]*N for _ in range(N)]
ans[0][0] = board[0][0]

for y in range(1, N):
    for x in range(y+1):
        if x > 0:
            ans[y][x] = max(ans[y-1][x-1], ans[y-1][x]) + board[y][x]
        else:
            ans[y][x] = ans[y-1][x] + board[y][x]

print(max(ans[N-1]))

4. 마치며

.