[백준] 1932번 정수 삼각형 파이썬(Python) 풀이

1932번: 정수 삼각형

---

[문제]

 

---

[코드]

import sys
input = sys.stdin.readline

n = int(input())
tree = []
for _ in range(n):
    tree.append([int(f) for f in input().split()])


for i in range(1, n):
    for j in range(0 , i+1):
        if j == 0:
            tree[i][0] += tree[i-1][0]
        elif j == i:
            tree[i][j] += tree[i-1][j-1]
        else:
            tree[i][j] += max(tree[i-1][j-1], tree[i-1][j])


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

---

[해석]

 

실버 1치고는 비교적 간단한 문제

 

처음에는 BFS, DFS 문제로 접근해서 풀어볼까 생각해보았지만

생각해보니까 그런 문제가 아니었다

dp를 이용한 greedy 문제에 가까운 문제였다

 

import sys
input = sys.stdin.readline

n = int(input())
tree = []
for _ in range(n):
    tree.append([int(f) for f in input().split()])

여기까지는 간단한 구현

tree 크기를 n변수로 받고 

for 문을 통해서 각 층에 해당하는 값을 list의 형태로 tree에 추가해준다

 

for i in range(1, n):
    for j in range(0 , i+1):
        if j == 0:
            tree[i][0] += tree[i-1][0]
        elif j == i:
            tree[i][j] += tree[i-1][j-1]
        else:
            tree[i][j] += max(tree[i-1][j-1], tree[i-1][j])


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

사실상 이 이중 for문에 문제 해결의 핵심 코드

먼저 첫번째 for 문은 1에서 시작해서 n까지 실행

     (why? not start 0 : 예제1의 예시로 설명하자면 5층인 tree는 -> 0층~4층까지 간다 (5층), 우리가 구하려고 하는 것은 최       댓값이기 때문에 1층에서 - 0층을 바라보고 2층에서 -1층을 바라보면서 최댓값을 구해야한다

     따라서 1~n까지 for문을 실행 = 0층은 스킵)

 

그리고 그 층에 해당하는 값들을 2번째 for문을 돌면서 이전 층의 값과 더해줌 

    (why? i+1까지인가 -> 각층의 값 1층[0층]의 값은 1개 , 2층[1층]의 값은 2개, 즉, n층[n-1층]의 값의 갯수는 n개 이므로 n      층의 전체 값을 돌기 위해서는 i-1까지 for문을 돌아야 한다)

 

 여기서 경우의 수는 3가지로 나옴

(1) 맨 왼쪽에 위치한 값을 경우

(2) 맨 오른쪽에 위치한 값일 경우

(3) 그외에 위치한 경우

 

 

(1), (2)번의 경우 무조건 하나의 값으로 갈 수 밖에 없다 - 특정 값을 향해 갈 수 밖에 없다는 소리

 

예제를 보았을 때 3층은 8, 1, 8 으로 구성되어 있다 

여기서 (1)은 맨 왼쪽 8 ->이는 위의 값 중 3으로 밖에 갈 수 밖에 없다

여기서 (2)는 맨 오른쪽 8 8 ->이는 위의 값 중 8로 갈 수 밖에 없다

그리고 나머지 경우 (3) -> 중앙 1 -> 이 친구는 3 or 8로 갈 수 있다

 

따라서 (1), (2)의 값은 특정 위치의 값을 더하게 만들어 주고 

(3) -> 경우의 수가 2가지 이기때문에 우리가 구하려고 하는 값 , 최댓값을 위해서 더 했을 때 최대가 되는 값을 더해준다

 

그렇게 for문을 돌면 완성

 

tree의 [n-1] 리스트의 최댓값을 출력해주면 우리가 구하려고 했던 값이 나온다