[파이썬][백준 1932][🤍실버 1] (다이나믹 프로그래밍)

🧞‍♂️ 난이도

🤍 실버 1

🧞‍♂️ 문제

최소 회의실 개수

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

🧞‍♂️ 유형

다이나믹 프로그래밍

🧞‍♂️ 내 풀이

이 문제는 다이나믹 프로그래밍으로 풀면 되는 문제이다.

입력 값에서 힌트를 얻을 수 있다

7
3 8
8 1 0
2 7 4 4
4 5 2 6 5

이런 형태 그대로 dp 배열이 만들어져있다고 상상하고 이중 for 문을 돌리면서 최대값을 구하면 된다. 11시 방향에 있는 값이랑 12시 방향에 있는 값을 계속해서 비교하고 더해가면서 최대값 구하면 된ㄷㅏ.

그럼 마지막 행에 남아있는 숫자들중 최대값이 답이 된다. ***

🧞‍♂️ 파이썬 풀이

import sys
input = sys.stdin.readline
N = int(input())
dp = []
for _ in range(N):
    dp.append(list(map(int, input().split())))

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

맨 위로 이동하기

BOJ 카테고리 내 다른 글 보러가기