[python] 백준 1932 - 정수 삼각형

출처 : 백준, https://www.acmicpc.net/problem/1932

1932번: 정수 삼각형

 

이거 푸니까 보람차다. 

프로그래머스에 동일한 문제가 있다.

 

 

2023.04.15 업데이트 풀이

 

def solution(triangle):
    # 7
    # 3 8
    # 8 1 0
    # 2 7 4 4
    # 4 5 2 6 5
    
    # 점화식은 triangle[i][j] = triangle[i][j] + max(triangle[i-1][j-1], triangle[i-1][j])
    
    answer = 0
    
    floor = len(triangle)
    
    for i in range(1, floor):
        floor_length = len(triangle[i])
        prev_floor_length = len(triangle[i - 1])
                           
        for j in range(floor_length):
            comp_list = []
            
            if 0 <= i-1 < floor and 0 <= j-1 < prev_floor_length:
                comp_list.append(triangle[i-1][j-1])

            if 0 <= i-1 < floor and 0 <= j < prev_floor_length:
                comp_list.append(triangle[i-1][j])

            triangle[i][j] += max(comp_list)
            
    return max(triangle[floor - 1])

---

첫 번째 풀이 : DFS - 시간초과

 

max_val = 0

def DFS(arr, floor, index, sum):
  global max_val
  if floor == len(arr) - 1:
    if max_val < sum:
      max_val = sum
  else:
    for i in range(index, index+2):
      sum += arr[floor+1][i]
      DFS(arr, floor+1, i, sum)
      sum -= arr[floor+1][i]

  return

if __name__ == '__main__':
  n= int(input())
  arr = []
  
  for i in range(n):
    arr.append(list(map(int, input().split())))

  sum = arr[0][0]
  
  DFS(arr, 0, 0, sum)
  
  print(max_val)

 

총 봐야하는 경우의 수가 2^(n+1)이길래 컴퓨터면 2^500개 정도는 2초 안에 비교할 수 있지 않을까? 했는데

........시간초과 걸렸다. 컴퓨터 생각보다 느리군.......

 

두 번째 풀이 : DP

 

def solution(n, arr):
  answer = [[] for _ in range(n)]

  #a00, a10, a11 세팅
  answer[0].append(arr[0][0])
  answer[1].append(arr[0][0] + arr[1][0])
  answer[1].append(arr[0][0] + arr[1][1])

  for i in range(2, n):
    #0번째 append
    answer[i].append(answer[i-1][0] + arr[i][0])
    #사이 append
    for j in range(0, len(answer[i-1]) - 1):
      base = answer[i-1][j] if answer[i-1][j] > answer[i-1][j+1] else answer[i-1][j+1]
      answer[i].append(base + arr[i][j+1])
    #나머지 append
    answer[i].append(answer[i-1][-1] + arr[i][-1])

  return max(answer[n-1])

if __name__ == '__main__':
  n = int(input())
  arr = []

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

  answer = solution(n, arr) if n > 1 else arr[0][0]
  print(answer)

 

---

 

시간 복잡도

 

O(N^2)

 

알게 된 점

 

_

 

고찰

 

점화식을 사용하는 용도가 비교군의 개수를 줄이기 위해서 사용되었다는게 신기한 풀이.

물론 DFS로하면 최대 2^500개를 비교해야하기 때문에 우리 하찮은 컴퓨터는 그런거 못해서 DP로 해야하지만....

지금까지 DP를 풀 때 항상 문제의 답을 도출하도록 규칙을 찾아 점화식을 끄집어내려고 했었는데,

그게 아니라 비교군을 줄이기 위해 겹치는 부분에 대해 DP를 사용하는 문제를 보니 편견이 깨진 느낌이다.