[Python Algorithm] 정수 삼각형 BOJ #1932

문제

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

1932번: 정수 삼각형

 

내 문제 풀이

n = int(input())
memory = [int(input())]

for _ in range(1, n):
    now = list(map(lambda x: int(x), input().split()))
    for i in range(len(now)):
        if i == 0:
            now[0] += memory[0]
        elif i == len(now)-1:
            now[-1] += memory[-1]
        else:
            if memory[i-1] > memory[i]: now[i] += memory[i-1]
            else: now[i] += memory[i]
    memory = now

print(max(memory))

👉 DP 문제로, 최소한의 탐색으로 최대 값을 만드는 경로를 찾는 것이 포인트!

• 모든 층에서는 최댓값을 만들기 위하여 윗 층의 대각선 앞, 혹은 뒤 중 더 큰 누적합의 수를 골라야 한다.
  #1149_RGB거리 문제 같은 경우에는 어떤 입력이 있든 3가지의 경우의 수로 추릴 수 있기 때문에
  처음부터 경우의 수를 구하기 위한 리스트를 모두 생성해놓고 시작했지만, 이 문제의 경우에는
  입력되는 N값에 따라 경우의 수가 무수히 많아질 수 있으므로 모든 경우의 수에 대한 리스트를 만들지 않고
  '윗 층(이전 층)'을 의미하는 memory 리스트와 '아랫 층(현재 층)'을 의미하는 now 리스트를 만들어서,
  계속하여 memory 리스트에 값을 누적하며 마지막에 저장된 memory 값 중 가장 큰 수를 고르면 된다.
• 한 가지 고려해줄 점은, 한 층의 가장 첫 번째 요소나 마지막 요소의 경우에는
  윗 층에서 두 가지 값을 선택할 수 없기 때문에 그 부분만 따로 예외로 빼주어서 처리했다.

 

💡 피드백

• 경우의 수를 어떻게 처리해줄 것인지만 생각하면 쉬운 문제가 될 것 같다.