[백준 1932] 파이썬 - 정수 산각형

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

1932번: 정수 삼각형

 

1. 코드 설명

n = int(input())

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

#tri = [[7], [3, 8], [8, 1, 0], [2, 7, 4, 4], [4, 5, 2, 6, 5]]

#n=5

for i in range(1,n):

    for j in range(i+1):

        if j == 0:

            tri[i][j] = tri[i][j] + tri[i-1][j]

            #print('j == 0 ',tri)

        elif i == j:

            tri[i][j] = tri[i][j] + tri[i-1][j-1]

            #print('i == j ',tri)

        else:

            tri[i][j] = max(tri[i][j]+tri[i-1][j], tri[i][j]+tri[i-1][j-1])

            #print('else ',tri)

        #print(tri)

        #print('****')

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

 

 

 

 

 

 

먼저 2중 for문을 다음과 같이 작성하면 문제에서 삼각형의 index를 출력할 수 있다.

# 인덱스 출력 tip

for i in range (n) :

  for j in range(i+1):

    print('i,j =' , i , j)

  print('****')

 

 

 

여기서 삼각형을 탐색하는 방법은 3가지로 나누어진다.

 

 

1) j == 0 인 경우

 

tri[i][j] = tri[i][j] + tri[i-1][j]

 

1번 처럼 아래로만 내려가는 경우이며

 

이는 현재 값( tri[i][j] ) 을 현재 값( tri[i][j] )과 직전 값( tri[i-1][j] )을 합한 값으로 바꾸어준다.

 

 

 

2) i == j 인 경우

 

tri[i][j] = tri[i][j] + tri[i-1][j-1]

 

사실상 1번과 같은 경우이다. 대각선 기준으로 현재 값을 현재 값과 직전 값의 합으로 바꾸어준다.

 

 

3) 나머지 경우

 

tri[i][j] = max(tri[i][j]+tri[i-1][j], tri[i][j]+tri[i-1][j-1])

 

왼쪽 대각선( tri[i-1][j] )과 오른쪽 대각선( tri[i-1][j-1] )중 더 큰 값을 현재 값에 저장한다.

 

 

 

 

 

2. 주의 사항

 

3) 의 케이스만 사용시 

 

 tri[i][j] = max(tri[i][j]+tri[i-1][j], tri[i][j]+tri[i-1][j-1]) 

 

1), 2) 처럼 양 끝에서 탐색하는 경우 i -1 , j - 1 에서 인덱스 초과 오류가 발생한다.

 

이것이 3가지 경우로 나누어 탐색하는 이유이다.