๋ฌธ์
https://www.acmicpc.net/problem/8980
๋ฐฑ์ค ๋ฌธ์ ์ง - 0x11๊ฐ - ๊ทธ๋ฆฌ๋
์๊ณ ๋ฆฌ์ฆ: ๊ทธ๋ฆฌ๋, ์ ๋ ฌ
ํ์ด
์ง์ ๋๋ก์์ ์ผ์ชฝ๋ถํฐ ์ค๋ฅธ์ชฝ์ผ๋ก 1๋ฒ๋ถํฐ ์ฐจ๋ก๋๋ก ๋ฒํธ๊ฐ ๋ถ์ฌ์ง ๋ง์๋ค์ด ์๋ค. ๋ง์์ ์๋ ๋ฌผ๊ฑด์ ๋ฐฐ์กํ๊ธฐ ์ํ ํธ๋ญ ํ ๋๊ฐ ์๊ณ , ํธ๋ญ์ด ์๋ ๋ณธ๋ถ๋ 1๋ฒ ๋ง์ ์ผ์ชฝ์ ์๋ค. ์ด ํธ๋ญ์ ๋ณธ๋ถ์์ ์ถ๋ฐํ์ฌ 1๋ฒ ๋ง์๋ถํฐ ๋ง์ง๋ง ๋ง์๊น์ง ์ค๋ฅธ์ชฝ์ผ๋ก ๊ฐ๋ฉด์ ๋ง์์ ์๋ ๋ฌผ๊ฑด์ ๋ฐฐ์กํ๋ค.
๊ฐ ๋ง์์ ๋ฐฐ์กํ ๋ฌผ๊ฑด๋ค์ ๋ฐ์ค์ ๋ฃ์ด ๋ณด๋ด๋ฉฐ, ๋ณธ๋ถ์์๋ ๋ฐ์ค๋ฅผ ๋ณด๋ด๋ ๋ง์๋ฒํธ, ๋ฐ์ค๋ฅผ ๋ฐ๋ ๋ง์๋ฒํธ์ ๋ณด๋ผ ๋ฐ์ค์ ๊ฐ์๋ฅผ ์๊ณ ์๋ค. ๋ฐ์ค๋ค์ ๋ชจ๋ ํฌ๊ธฐ๊ฐ ๊ฐ๋ค. ํธ๋ญ์ ์ต๋๋ก ์ค์ ์ ์๋ ๋ฐ์ค์ ๊ฐ์, ์ฆ ํธ๋ญ์ ์ฉ๋์ด ์๋ค. ์ด ํธ๋ญ ํ๋๋ฅผ ์ด์ฉํ์ฌ ๋ค์์ ์กฐ๊ฑด์ ๋ชจ๋ ๋ง์กฑํ๋ฉด์ ์ต๋ํ ๋ง์ ๋ฐ์ค๋ค์ ๋ฐฐ์กํ๋ ค๊ณ ํ๋ค.
์กฐ๊ฑด 1: ๋ฐ์ค๋ฅผ ํธ๋ญ์ ์ค์ผ๋ฉด, ์ด ๋ฐ์ค๋ ๋ฐ๋ ๋ง์์์๋ง ๋ด๋ฆฐ๋ค.
์กฐ๊ฑด 2: ํธ๋ญ์ ์ง๋์จ ๋ง์๋ก ๋๋์๊ฐ์ง ์๋๋ค.
์กฐ๊ฑด 3: ๋ฐ์ค๋ค ์ค ์ผ๋ถ๋ง ๋ฐฐ์กํ ์๋ ์๋ค.
๋ง์์ ๊ฐ์, ํธ๋ญ์ ์ฉ๋, ๋ฐ์ค ์ ๋ณด(๋ณด๋ด๋ ๋ง์๋ฒํธ, ๋ฐ๋ ๋ง์๋ฒํธ, ๋ฐ์ค ๊ฐ์)๊ฐ ์ฃผ์ด์ง ๋, ํธ๋ญ ํ ๋๋ก ๋ฐฐ์กํ ์ ์๋ ์ต๋ ๋ฐ์ค ์๋ฅผ ๊ตฌํ๋ ํ๋ก๊ทธ๋จ์ ์์ฑํ์์ค. ๋จ, ๋ฐ๋ ๋ง์๋ฒํธ๋ ๋ณด๋ด๋ ๋ง์๋ฒํธ๋ณด๋ค ํญ์ ํฌ๋ค.
์ ๋ ฌ ๊ธฐ์ค์ด ํคํฌ์ธํธ์ธ ๋ฌธ์ ๋ค.
๋ง์ ์ํ๊ฐ 1 ~ N ์์ผ๋ก ์ด์ด์ ธ์ ๋ณด๋ด๋ ๋ง์ ๊ธฐ์ค์ผ๋ก ์ ๋ ฌํ์ง๋ง ํ๋ฆฐ ๋ฐฉ๋ฒ์ด์๋ค ^^;
์ ์ฌํ ์ ์๋ ํ๋ฐฐ์ ์์ด ์ ํด์ ธ์์ผ๋ฏ๋ก, ํธ๋ญ ๊ณต๊ฐ์ ์ต๋ํ ๋นจ๋ฆฌ ๋น์ธ์๋ก ๊ฐ๋ฅํ ์ ์ฌ๋์ด ๋์ด๋๋ค!
๋ฐ๋ผ์ ๋ฐฐ์ก ๋ฆฌ์คํธ๋ฅผ "๋ฐ๋ ๋ง์" ์์ผ๋ก ์ค๋ฆ์ฐจ์ ์ ๋ ฌํด์ผํ๋ค.
๋ํ ์ฌ์ ๊ณต๊ฐ์ ๋ฐ๋ผ ์ฃ์ ์ ์๋ ํ๋ฐฐ๋์ด ๋ฌ๋ผ์ง๋ฏ๋ก, ๊ฐ ๋ง์์์์ ํธ๋ญ ์ฉ๋์ ๊ธฐ๋กํ๋ค.
boxes = [tuple(map(int, input().split())) for _ in range(M)]
boxes.sort(key=lambda x: x[1]) # ๋ฐ๋ ๋ง์ ๋ฒํธ ๊ธฐ์ค์ผ๋ก ์ ๋ ฌ
capacity = [C] * (N + 1) # ๊ฐ ๋ง์์ ํธ๋ญ ์ต๋ ์ฉ๋
์์์ ์ ๋ ฌํ ๋ฐฐ์ก ๋ฆฌ์คํธ๋ฅผ ์ํํ๋ฉฐ ํธ๋ญ ์ฉ๋๊ณผ ๋ฐฐ์กํ ๋ฐ์ค ์๋ฅผ ์ ๋ฐ์ดํธํ๋ค.
๊ฐ ๋ฆฌ์คํธ๋ (๋ณด๋ด๋ ๋ง์, ๋ฐ๋ ๋ง์, ํ๋ฐฐ์์ ์)๋ก ๊ตฌ์ฑ๋์ด์๋ค. ์ด๋ฅผ (s, e, box)๋ก ์ํํ๋ค๊ณ ๊ฐ์ ํด๋ณด์.
ํธ๋ญ์ ์ฌ์ ๊ณต๊ฐ์ ๋ฐ๋ผ ์ฃ์ ์ ์๋ ํ๋ฐฐ์ ์๊ฐ ๋ฌ๋ผ์ง๋ฏ๋ก, ์ฌ์ ๊ณต๊ฐ๋ถํฐ ์ฒดํฌํด์ผํ๋ค.
๋จผ์ ํธ๋ญ ์ฉ๋ ๋ฆฌ์คํธ์ s๋ถํฐ e-1๋ฒ์งธ๊น์ง์ ๊ฐ ์ค ๊ฐ์ฅ ์์๊ฐ์ ์ฐพ๋๋ค.
์ด์ฐจํผ ํ๋ฐฐ๋ e ๋ง์์ ๋์ฐฉํ๋ฉด ๋ด๋ฆด๊ฒ์ด๋ฏ๋ก e-1๋ฒ์งธ ๋ง์๊น์ง์ ์ฌ์ ๊ณต๊ฐ๋ง ์ฒดํฌํ๋ฉด ๋๋ค.
๋ํ e-1๋ฒ์งธ ๋ง์๊น์ง ์ญ ์ฃ๊ณ ์์ด์ผํ๋ฏ๋ก ์ต์๊ฐ์ ๊ตฌํด์ผํ๋ค.
๊ทธ๋ฆฌ๊ณ ๋ณธ๋ ์ค์ผ๋ ค ํ๋ box์ ์์์ ๊ตฌํ ์ต์๊ฐ์ ๋น๊ตํ์ฌ ๋ ์์๊ฐ๋งํผ์ ํธ๋ญ์ ์ฃ๋๋ค.
์ค์์ผ๋ฉด ์ฌ์ ๊ณต๊ฐ์ ์์ ํด์ค์ผํ๋ค.
ํธ๋ญ ๊ณต๊ฐ ๋ฆฌ์คํธ๋ฅผ s๋ถํฐ e-1๋ฒ์งธ๊น์ง ์ํํ๋ฉฐ ์ค์ ์ค์ ํ๋ฐฐ ์ ๋งํผ ๋นผ์ค๋ค.
๋ค์ ์ํ๋ก ๋์ด๊ฐ๊ธฐ ์ ๋ฐฐ์กํ ๋ฐ์ค ์์ ์ค์ ํ๋ฐฐ ์๋ฅผ ๋ํ๋ค.
์ ์ฒด ์ฝ๋
# โญ ๋ฐ๋ ๋ง์ ๊ธฐ์ค์ผ๋ก ์ ๋ ฌํด์ผํจ. ํธ๋ญ ๊ณต๊ฐ์ ๋ ๋นจ๋ฆฌ ๋น์ธ์๋ก ๊ฐ๋ฅํ ์ ์ฌ๋์ด ๋์ด๋๊ธฐ ๋๋ฌธ!
# ๋ฉ๋ชจ๋ฆฌ: 34456KB / ์๊ฐ: 960ms
from sys import stdin
input = stdin.readline
N, C = map(int, input().split())
M = int(input())
boxes = [tuple(map(int, input().split())) for _ in range(M)]
boxes.sort(key=lambda x: x[1]) # ๋ฐ๋ ๋ง์ ๋ฒํธ ๊ธฐ์ค์ผ๋ก ์ ๋ ฌ
capacity = [C] * (N + 1) # ๊ฐ ๋ง์์ ํธ๋ญ ์ต๋ ์ฉ๋
total_box = 0
for s, e, box in boxes:
available = min(capacity[s:e]) # s ~ e ๋ง์ ์ฌ์ด์์ ๊ฐ๋ฅํ ์ต๋ ๊ณต๊ฐ
max_box = min(box, available) # ์ค์ ๋ก ๋ฐฐ์ก ๊ฐ๋ฅํ ์์ ์
for i in range(s, e):
capacity[i] -= max_box # ๊ฐ๋ฅํ ์์ ์๋งํผ s ~ e ๊ณต๊ฐ ์
๋ฐ์ดํธ
total_box += max_box
print(total_box)
์ฐธ๊ณ ๋ก ์ฃผ๋ ๋ง์์ ์์๋ ๊ณ ๋ คํ์ง ์์๋ ๋๋ค. ์ด์ฐจํผ ํธ๋ญ์ ํญ์ ์ผ์ชฝ์์ ์ค๋ฅธ์ชฝ์ผ๋ก ์งํ๋๋ฏ๋ก, ์ด๋ ๋ง์์ ๋จผ์ ๋ฐ์ง๋ ์ต์ข ์ ์ฌ๋์ ๊ฐ๊ฒ๋๋ค.
์๋ฆฌ๊น๋ฆฌ ํ๋ค๋ฉด ์์์ ํจ๊ป ๋ณด์.
6 60
5
1 2 30
2 5 70
5 6 60
3 4 40
1 6 40
# ๋ต: 150
์์ 2๋ฒ์ด๋ค.
๋ฐ๋ ๋ง์ ๊ธฐ์ค์ผ๋ก ์ค๋ฆ์ฐจ์ ์ ๋ ฌํ๋ฉด ์๋์ ๊ฐ๋ค.
1 2 30
3 4 40
2 5 70
5 6 60
1 6 40
์ฒซ๋ฒ์งธ๋ถํฐ ๋ง์ง๋ง๊น์ง ์ํ ๊ณผ์ ์ด๋ค.
# ์ฒซ๋ฒ์งธ ์ํ
capacity = [60, 60, 60, 60, 60, 60, 60]
total_box = 0
s, e, box = 1, 2, 30
min(capacity[s:e]) = 60
min(60, box) = 30
# ๋๋ฒ์งธ ์ํ
capaticy = [60, 30, 60, 60, 60, 60, 60]
total_box = 30
s, e, box = 3, 4, 40
min(capacity[s:e]) = 60
min(60, box) = 40
# ์ธ๋ฒ์งธ ์ํ
capaticy = [60, 30, 60, 20, 60, 60, 60]
total_box = 70
s, e, box = 2, 5, 70
min(capacity[s:e]) = 20
min(20, box) = 20
# ๋ค๋ฒ์งธ ์ํ
capacity = [60, 30, 40, 0, 40, 60, 60]
total_box = 90
s, e, box = 5, 6, 60
min(capaticy[s:e]) = 60
min(60, box) = 60
# ๋ค์ฏ๋ฒ์งธ ์ํ
capacity = [60, 30, 40, 0, 40, 0, 60]
total_box = 150
s, e, box = 1, 6, 40
min(capatity[s:e]) = 0
min(0, box) = 0
# ์ํ ํ ๊ฒฐ๊ณผ
capacity = [60, 30, 40, 0, 40, 0, 60]
total_box = 150