백준 19622 - 회의실 배정 3

문제설명

제한사항 및 입출력

 

풀이

문제를 잘 읽어보면 제한사항에 k번째 회의는 k-1, k+1과 겹치지만 다른 회의랑은 겹치지 않는다는 것을 알 수 있다. 해당 조건으로 회의의 시작 시간, 종료 시간은 필요가 없어지는 정보가 된다. 핵심은 인접한 것을 선택하지 못한다는 것이다.

 

기초적인 dp 문제라고 생각했다. 현재 값을 선택하거나, 선택하지 않거나.

dp[i] = i번째 회의까지 진행했을 때 최대 인원

상태전이: max(해당 회의를 선택했다면 i-2 + 현재, 해당 회의를 선택하지 않았다면 i-1)

내 코드

import sys
input = sys.stdin.readline
mis = lambda: map(int, input().split())

n = int(input())
num = []
for _ in range(n):
    num.append([*mis()][2])

dp = [0] * n
dp[0] = num[0]
if n == 1:
    print(dp[-1])
    exit()
dp[1] = max(num[0], num[1])
for i in range(2, n):
    dp[i] = max(dp[i-1], dp[i-2] + num[i])

print(dp[-1])

 

고찰

복잡하다면 2차원 dp로도 풀이할 수 있다. 

 

dp테이블 정의

dp[i][0] = i번째 회의를 선택한 경우 최댓값

dp[i][1] = i번째 회의를 선택하지 않은 경우 최댓값

 

상태전이

dp[i][0] = 이전 회의를 선택하지 않은 경우 + 현재 회의를 선택한 경우

dp[i][1] = max(이전 회의를 선택한 경우, 이전 회의를 선택하지 않은 경우)

 

개인적으로는 2차원 테이블을 사용하는 것이 이전의 최댓값을 직관적으로 식별하기 더 편한 것 같아 좀 더 직관적이라고 생각한다.

n = int(input())
num = []
for _ in range(n):
    num.append([*mis()][2])

dp = [[0, 0] for _ in range(n)]
dp[0] = [num[0], 0]
if n == 1:
    print(max(dp[-1]))
    exit()
for i in range(1, n):
    dp[i][0] = dp[i-1][1] + num[i]
    dp[i][1] = max(dp[i-1][0], dp[i-1][1])

print(max(dp[-1]))