백준 1932 문제 풀이 python

🐒 정수 삼각형

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

✍ 나의 풀이

import sys



n = int(input())


arr = []
for _ in range(n):
    arr.append(list(map(int,sys.stdin.readline().split())))

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

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

딱 30분 걸려서 푼 문제이다.

---

🧠 문제 이해

    7
  3   8
5   1   0

위와같은 정수 삼각형이 있을때
꼭대기에서부터 대각선으로 내려오면서 숫자를 합할때의 최댓값을 구해야한다.

     7
  10   16
15   17   16

따라서 마지막줄에서 가장 큰 17을 출력할 수 있어야한다.

나는 dp테이블을 따로 만들기 어려울 것 같아서 그냥 주어진 배열에 값을 저장해야겠다고 생각했다.

셋째줄의 1은 두번째줄의 3 또는 8 중에서 더 큰 숫자인 8을 합하게 되는 방식이다.

입력은

7
3 8
5 1 0 

위 같은 형태로 이루어지므로

arr = [[7],[3,8],[5,1,0]]

처럼 입력을 저장할 수있다.

셋째줄의 1은 arr[2][1]이고
둘째줄의 3 또는 8에서 큰 수를 찾아서 합해야하니 

arr[2][1] = max(arr[1][0] , arr[1][1]) + arr[2][1] 로 합한 값을 1이 있던 자리에 저장할 수 있다.

for i in range(1,n):
    for j in range(len(arr[i])):
            arr[i][j] = max(arr[i][j] + arr[i-1][j-1] , arr[i][j] + arr[i-1][j])

따라서 위의 반복문으로 구할 수 있으나

찾으려는 값이 삼각형의 모서리에 위치하면 합할 수 있는 값은 하나이므로 조건을 추가했다.

for i in range(1,n):
    for j in range(len(arr[i])):
        if j == 0:
         #삼각형의 왼쪽 모서리일때
            arr[i][j] = (arr[i][j] + arr[i-1][j])
        elif j == len(arr[i]) -1:
        #삼각형의 오른쪽 모서리일때
            arr[i][j] = (arr[i][j] + arr[i-1][j-1])
        else:
            arr[i][j] = max(arr[i][j] + arr[i-1][j-1] , arr[i][j] + arr[i-1][j])

---

🛠리팩토링

코드를 간단하게 정리하고,

삼각형의 각 층의 길이가 일정하게 1씩 증가하는 규칙이 있으므로 연산을 줄이기 위해
변수 k를 새로 만들었다.

import sys



n = int(input())


arr = []
for _ in range(n):
    arr.append(list(map(int,sys.stdin.readline().split())))

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

코드를 바꿨더니 메모리 사용량이 늘고, 처리시간이 줄었다.