[BOJ] 1932 정수 삼각형 - python

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

1932번: 정수 삼각형

• 풀이 방법

  모든 경로를 다 돌면서 최대 cost를 찾는거니까 완전탐색? 가만있어봐 보니까 경로 내려가면서 겹치는게 있잖아? → dp테이블 이용! 각 층, 각 칸의 상황을 저장 해 놓을 수 있는 dp테이블을 만들자

최종 코드

import sys

def input():
    return sys.stdin.readline().rstrip()

#일단 모든 경로를 다 돌긴 해야하는데, dp테이블 사용해서 시간 줄이기 가능
#삼각형크기는 1 이상 500 이하
#대각선 왼쪽 혹은 대각선 오른쪽만 이동 가능 ->
    # N층 이동하면서 다 더할건데, N층 이동하면 return

N = int(input())
T = [list(map(int,input().split())) for _ in range(N)]
#print(T)

dp = [([0] * N) for _ in range(N)] #n층,n개 만큼의 캐시를 만들어 놓음
visited = 0

def dfs(floor, num):
    #종료조건 : 마지막 층, 마지막 애까지 다 했을 떄
    if floor == (N-1):
        return T[floor][num]

    #dp테이블 이용
    if dp[floor][num] != 0:
        return dp[floor][num]

    #가지치기
    dp[floor][num] = max(dp[floor][num], dfs(floor + 1, num) + T[floor][num])
    dp[floor][num] = max(dp[floor][num], dfs(floor + 1, num + 1) + T[floor][num])

    return dp[floor][num]

#Top-down으로 0층에 0번째 애부터 시작한다고 알림
print(dfs(0,0))

얻어가는 것

• Dynamic programming (DP)→ 이전 값을 저장해 놓을 cache가 필요하다.

  def dfs(n):
  	#종료조건
  	if 종료시:
  		return 마지막 값 혹은 그냥 리턴
  	if dp테이블에 존재:
  		return dp[n] 테이블 값 리턴
  	
  	#가지치기 시작! (가능한 모든 경우 탐색)
  	for i in range(..):
  		dp[n] = 수식 어쩌구 저쩌구, 갱신도 진행
  	return dp[n]
  
  print(dfs[시작조건])
  

• → 종료조건 , dp 테이블 이용 , 가지치는 부분 (총 3가지 부분이 필요)
• : sub problem으로 쪼갤 수 있는가? 진짜 중복 호출되는가?

느낀점

"211001"

소요 시간 : 30분

• 모든 루트를 지나가고, 경로가 일부 겹친다면 dynamic programming을 이용하자!
• 어제랑 비슷한 문제를 풀어서 그런지 생각보다 쉽게 풀렸다.