[ 백준 1932 ] ( python ) 정수 삼각형

 

📚 정수 삼각형

 

문제

        7
      3   8
    8   1   0
  2   7   4   4
4   5   2   6   5

위 그림은 크기가 5인 정수 삼각형의 한 모습이다.

맨 위층 7부터 시작해서 아래에 있는 수 중 하나를 선택하여 아래층으로 내려올 때, 이제까지 선택된 수의 합이 최대가 되는 경로를 구하는 프로그램을 작성하라. 아래층에 있는 수는 현재 층에서 선택된 수의 대각선 왼쪽 또는 대각선 오른쪽에 있는 것 중에서만 선택할 수 있다.

삼각형의 크기는 1 이상 500 이하이다. 삼각형을 이루고 있는 각 수는 모두 정수이며, 범위는 0 이상 9999 이하이다.

입력

첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ 500)이 주어지고, 둘째 줄부터 n+1번째 줄까지 정수 삼각형이 주어진다.

출력

첫째 줄에 합이 최대가 되는 경로에 있는 수의 합을 출력한다.

예제 입력 1 복사

5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5

예제 출력 1 복사

30

 

 

 

✍ 접근

• 나..  DP 못하네
• 삼각형을 그리면서 방법을 찾는다

 

 

정답 코드 1

import sys
input = sys.stdin.readline
N = int(input())
arr = []
for _ in range(N):
    arr.append(list(map(int,input().split())))
res=[arr[0][0]]
for i in range(1,N):
    for j in range(len(arr[i])):
        if j == 0:
            arr[i][0] = arr[i-1][0]+arr[i][0]
        elif j == len(arr[i])-1:
            arr[i][-1] = arr[i-1][-1]+arr[i][-1]
        else:
            arr[i][j] = max(arr[i-1][j-1],arr[i-1][j])+arr[i][j]
print(max(arr[N-1]))

 

 

정답 코드 2

import sys
input = sys.stdin.readline
N = int(input())
arr = []
for _ in range(N):
    arr.append(list(map(int,input().split())))
res=[arr[0][0]]
for i in range(1,N):
    arr[i][0] = arr[i-1][0]+arr[i][0]
    arr[i][-1] = arr[i-1][-1]+arr[i][-1]
    for j in range(1,len(arr[i])-1):
        arr[i][j] = max(arr[i-1][j-1],arr[i-1][j])+arr[i][j]
print(max(arr[N-1]))

 

• 두 정답 코드의 차이는 단지 삼각형의 0번째 요소와 마지막 요소를 어디서 확인하냐의 차이. 두 번재 코드가 더 효율이 좋다 ( 한번만 확인하고 넘어가니까 + for문을 더 적게 도니까 192 -> 164)
• arr 에 삼각형을 넣어준다. arr에 있는 이중 배열은 1, 2, 3, 4 로 하나씩 커진다
• for문을 돌면서 arr[i][0]과 arr[i][1] 처음과 마지막은 바로 위 처음과 마지막 + 자신의 처음과 마지막 값을 해주고
  
  • 이중 for문을 통해 나머지 1부터 len(arr[i])-1 까지 돌며 arr[i][j] = max(왼쪽에서 왔을 때, 오른쪽에서 왔을 때)+ 자신의 값 

을 돌아주면 된다

 

 

⭐ 배움

• 일단 혼자 끝까지 풀어보는 것이 중요한 것 같다. 하지만.. 시간이 너무 소요될 시 정답을 확인하고 다시 풀어보는 것도 좋은 배움이 된다
• 유연한 사고를 가지자!