정수 삼각형

크기가 5인 정수 삼각형이 있다.

맨 위층에서 부터 아래에 있는 수 중 하나를 선택하여 아래층으로 내려올 때, 이제까지 선택된 수의 합이 최대가 된느 경로 구하기.

아래층에 있는 수는 현재층에서 선택된 수의 대각선 왼쪽 또는 대각선 오른쪽에 있는 것 중에서만 선택가능.

 

첫째줄에 삼각형의 크기

둘째줄에 정수삼각형이 한행씩 입력된다.

 

내 생각 

:금광문제와 유사하다는 생각이 들었다. dp테이블을 2차원으로 만들고, 최대값으로 갱신해 나가서 마지막에 최대값을 가져오면 된다고 생각했다. 다만 이문제 같은 경우, 한줄로 주는게 아니므로 append할 때 슬라이싱을 사용할 필요가 없다.

한줄 씩 넣는 방식을 생각했다.

제약조건은 금광문제와 비슷하게 대각선왼쪽, 오른쪽 수가 없는 경우를 생각했다.

 

부족했던 부분 

:

1.일단 한줄 씩 넣는 부분을 제대로 짜는데 실패했다.

dp.append(input().split()) 으로 넣었는데, 전부 str형으로 들어가서 실패했다.

dp.append( list(map(int, input().split()) ) )으로 넣었어야 했다. 이러면 전부 int형 리스트로 들어가서 알아서 dp에 자리잡았다.

 

2.for문을 설정하는 과정에서 열부분을 1작게 하는 실수를 했다.

for i in range(1,size):

 for j in range(i):  이렇게 하면 두번째 for문인 열이  size가 5일 경우 0~4까지 열이 진행되야 되는데 3까지만 진행되게 된다. 

 

따라서 for i in range(1,size):

 for j in range(i+1): 이 맞았다.

 

3. 예외조건을 처리할 때 else:를 안써서 잘못처리 됐던것 같다.

 

풀이:

 

#삼각형 크기 입력받기
size= int(input())
#정수삼각형 입력받기
dp=[]
for i in range(size):
dp.append( list(map( int,input().split()) ) ) 


#각각의 정수 삼각형 자리를 최대값으로 바꾼다
for i in range(1,size):
   for j in range(i+1):
   #1 대각선 왼쪽에서 왔을 경우
   if j==0:
   left=0
   else:
   left=dp[i-1][j-1]
   

#2 대각선 오른쪽에서 왔을 경우
   if j==i:
   right=0
   else:
   right=dp[i-1][j]

   #최대값 갱신
   dp[i][j]=dp[i][j]+max(left,right)

print( max( dp[size-1]) )