백준 #1932

난이도 : 실버1
소요시간 :  1h 17m
사용한 풀이법 : DP

---

풀이 과정

• 풀이과정(백트래킹)
  1. 각 요소[i][j]는 대해서 [i+1][j],[i+1][j+1]만 더할 수 있음
  2. 해당 위치에서 이동가능한 경로를 인자로 해서 함수 재귀 진행
  3. 인자가 n과 같아지면 결과갑 리스트에 삽입
  4. 모든 경우의 수 탐색 후 리스트의 max를 출력하면 정답!!
  5. 이긴 한데 메모리 초과 뜸
• 풀이과정(DP)
  1. 위에꺼에서 아래꺼를 더하는 방식이 아닌 아래꺼에서 위에 값을 참조해오는 것으로 변경
     =>메모리 손실 방지
  2. 참조 방식은 총 3가지
     1. 행의 첫번째 인자일 경우, 바로 위 행의 첫번째 인자값에 더하면 됨 ([i-1][0])
     2. 행의 마지막 인자일 경우, 바로 위 행의 마지막 인자값에 더하면 됨 ([i-1][-1])
     3. 행의 중간일 경우, 바로 위의 인자값과 왼쪽 대각선 위의 인자값 중 큰 값과 더하면 됨 (max([i-1][j], [i-1][j-1]))
  3. 쭉 참조하다가 리스트의 마지막 행에 도달하면 그 행의 최댓값이 곧 정답!

작성 코드

### 백트래킹으로 푼 방법

n = int(input())
tri = [[-1]*n for _ in range(n)]    #삼각형을 이루는 정수값 입력용 리스트
max_sum = []

cnt = 0
for i in range(n):
    row = input().split()
    for j in range(i+1):
        tri[i][j]=int(row[j])
    
def BackT(row,col,sum):
    if row==n:
        max_sum.append(sum)
        return 0
    
    sum += tri[row][col]
    BackT(row + 1, col, sum)
    BackT(row + 1, col + 1, sum)
    
BackT(0,0,0)
print(max(max_sum))

### DP로 푼 방법

n = int(input())
tri = []  #삼각형을 이루는 정수값 입력용 리스트

for _ in range(n):
    tri.append(list(map(int,input().split())))
    

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

피드백

'뭐야 백트래킹이네' 하고 풀었다가 된통 당한 멍청이 한명. 좀만 더 생각했으면 더 간결한 코드로 쉽게쉽게 풀었을텐데...
아 그리고 공백으로 구분된 문자열의 입력을 정수형 리스트에 넣는게 생각보다 헷갈린다. 
파이썬은 뭔가 굉장히 쉬운 언어이면서도 헷갈리는 언어다..