[Gold IV] 32187 - 급식 배식

문제

 1$1$부터 N$N$까지의 번호가 붙어있는 N$N$개의 배식대가 있다. i$i$번 배식대에서는 i$i$번 음식을 배식받을 수 있다. M$M$명의 학생들이 음식을 받기 위해 줄을 섰다.

각 학생은 특정 음식을 배식받을 수 있고, 배식받은 음식에 해당하는 만큼 행복도가 상승한다. 구체적인 규칙은 다음과 같다.

•  j$j$번 학생은 배식받을 수 있는 음식의 번호 pj,1,pj,2,⋯,pj,lj$p_{j,1},\,p_{j,2},\,\cdots,\,p_{j,l_j}$가 정해져 있다. 각 학생은 같은 음식을 최대 한 번만 배식받을 수 있다.
•  j$j$번 학생이 pj,k$p_{j,k}$번 음식을 배식받을 경우 학생의 행복도가 vj,k$v_{j,k}$만큼 상승한다.
•  j$j$번 학생이 배식받은 음식은 j+1$j+1$번 학생이 배식받을 수 없다. (1≤j≤M−1)$(1\leq j\leq M-1)$ 

초기에 모든 학생의 행복도는 0$0$이다. 학생들의 행복도 합이 최대가 되도록 배식을 진행해 보자!

입력

첫 번째 줄에 두 정수 N$N$과 M$M$이 공백으로 구분되어 주어진다. (1≤N,M≤105)$(1\leq N,M\leq10^5)$ 

이후 각 학생이 먹을 수 있는 음식에 대한 정보가 M$M$개의 줄에 걸쳐 주어진다.

정보의 j$j$번째 줄에는 j$j$번 학생이 먹을 수 있는 음식의 개수를 나타내는 정수 lj$l_j$가 가장 먼저 주어지고, 이후 2lj$2l_j$개의 정수 pj,1,vj,1,pj,2,vj,2,⋯,pj,lj,vj,lj$p_{j,1},\,v_{j,1},\,p_{j,2},\,v_{j,2},\,\cdots,\,p_{j,l_j},\,v_{j,l_j}$가 공백으로 구분되어 주어진다. 이때 pj,k$p_{j,k}$는 증가하는 순서로 주어진다. (1≤j≤M;$(1\leq j\leq M;$ 1≤lj≤N;$1\leq l_j\leq N;$ 1≤pj,1<pj,2<⋯<pj,lj≤N;$1\leq p_{j,1}<p_{j,2}<\cdots<p_{j,l_j}\leq N;$ 1≤vj,k≤109)$1\leq v_{j,k}\leq10^9)$ 

모든 lj$l_j$의 합은 105$10^5$을 넘지 않는다.

출력

학생들의 행복도 합의 최댓값을 출력한다.

예제 입력 1 복사

5 5
2 1 5 2 6
1 2 5
1 3 5
1 4 5
1 5 5

예제 출력 1 복사

26

 1$1$번 학생이 1$1$, 2$2$번 음식을 배식받고, 3$3$, 4$4$, 5$5$번 학생이 각각 3$3$, 4$4$, 5$5$번 음식을 배식받으면, 학생들의 행복도의 합은 (5+6)+0+5+5+5=26$(5 + 6) + 0 + 5 + 5 + 5 = 26$이 된다. 이 방법보다 행복도의 합을 크게 할 수 있는 방법은 없으므로, 답은 26$26$이 된다.

---

# 풀이 방법

• food_list[p]: 음식 p를 원하는 (학생 번호, 만족도) 리스트
• 각 음식에 대해, 그 음식을 원하는 학생들을 순서대로 보면서:
  • 현재 학생이 이전 학생 바로 다음이라면→ 이전-이전까지의 최대값 + 현재 만족도와 비교해서 더 큰 값 선택
  • → 연속된 두 학생이므로 같이 먹을 수 없음
  • 그 외의 경우 (연속 아님)
  • → 그냥 이전까지의 최대 만족도에 현재 만족도를 더함
• 즉, 음식별로 최대 만족도 합을 구하는 DP를 수행
• 최종적으로, 모든 음식의 최대 누적 만족도 합을 더하면 정답

→ dp문제 푸는거 여전히 익숙하지 않음 🥲

---

# 코드

import sys
sys.stdin = open("input.txt","r")

n, m = map(int, sys.stdin.readline().split())

food_list = [[] for _ in range(n+1)] # 음식별로 (학생번호, 만족도) 저장
hpy_dp = [[] for _ in range(n+1)] # 누적 행복지수 저장

for i in range(1, m+1): # 모든 학생
    tmp = list(map(int,sys.stdin.readline().split()))
    for j in range(tmp[0]):
        food = tmp[2*j+1]
        hpy = tmp[2*j+2]
        food_list[food].append((i,hpy))

result_hpy = 0
for food in range(1,n+1):
    # 음식을 먹을 수 있는 학생이 없는 경우
    if len(food_list[food]) == 0: continue

    hpy_dp[food].append(0)
    hpy_dp[food].append(food_list[food][0][1]) # 첫번째 학생의 만족도 저장

    for i in range(1, len(food_list[food])):
        curr_stu, curr_hpy = food_list[food][i]
        pre_stu, _ = food_list[food][i-1]

        hpy_dp[food].append(hpy_dp[food][-1]+curr_hpy)
        
        # 직전 학생이 이 음식 배정받았으면 수정해야 함
        if pre_stu + 1 == curr_stu:
            tmp_hpy = hpy_dp[food][-3] + curr_hpy
            if hpy_dp[food][-2] < tmp_hpy:
                hpy_dp[food][-1] = tmp_hpy
            else:
                hpy_dp[food][-1] = hpy_dp[food][-2]
    
    result_hpy += hpy_dp[food][-1]


print(result_hpy)

---

# 참고

---

아래 조건을 아예 무시하고 푼 코드..

(1) 같은 음식을 여러명이 배식받을 수 있는거

(2) j번 학생이 배식받은 음식은 j+1번 학생이 배식받을 수 없는

import sys
sys.stdin = open("input.txt","r")
n, m = map(int,sys.stdin.readline().split()) # n: 배식대, m: 학생 수
food = [0] * (n+1)
for _ in range(m):
    s = list(map(int,sys.stdin.readline().split()))
    for i in range(s[0]): # 음식의 길이만큼 반복문 돌기
        j = 2 * i + 1
        # s[j]: 음식 이름 / s[j+1]: 만족도
        if food[s[j]] < s[j+1]:
            food[s[j]] = s[j+1]

print(sum(food))