๋ฌธ์
https://www.acmicpc.net/problem/2457
๋ฐฑ์ค ๋ฌธ์ ์ง - 0x11๊ฐ - ๊ทธ๋ฆฌ๋
์๊ณ ๋ฆฌ์ฆ: ๊ทธ๋ฆฌ๋, ์ ๋ ฌ
ํ์ด
์ด N๊ฐ์ ๊ฝ์ด ์๋ ๋ฐ, ๊ฝ์ ๋ชจ๋ ๊ฐ์ ํด์ ํผ์ด์ ๊ฐ์ ํด์ ์ง๋ค. ํ๋์ ๊ฝ์ ํผ๋ ๋ ๊ณผ ์ง๋ ๋ ์ด ์ ํด์ ธ ์๋ค. ์๋ฅผ ๋ค์ด, 5์ 8์ผ ํผ์ด์ 6์ 13์ผ ์ง๋ ๊ฝ์ 5์ 8์ผ๋ถํฐ 6์ 12์ผ๊น์ง๋ ๊ฝ์ด ํผ์ด ์๊ณ , 6์ 13์ผ์ ํฌํจํ์ฌ ์ดํ๋ก๋ ๊ฝ์ ๋ณผ ์ ์๋ค๋ ์๋ฏธ์ด๋ค. (์ฌํด๋ 4, 6, 9, 11์์ 30์ผ๊น์ง ์๊ณ , 1, 3, 5, 7, 8, 10, 12์์ 31์ผ๊น์ง ์์ผ๋ฉฐ, 2์์ 28์ผ๊น์ง๋ง ์๋ค.)
์ด๋ฌํ N๊ฐ์ ๊ฝ๋ค ์ค์์ ๋ค์์ ๋ ์กฐ๊ฑด์ ๋ง์กฑํ๋ ๊ฝ๋ค์ ์ ํํ๊ณ ์ถ๋ค.
1. ๊ณต์ฃผ๊ฐ ๊ฐ์ฅ ์ข์ํ๋ ๊ณ์ ์ธ 3์ 1์ผ๋ถํฐ 11์ 30์ผ๊น์ง ๋งค์ผ ๊ฝ์ด ํ ๊ฐ์ง ์ด์ ํผ์ด ์๋๋ก ํ๋ค.
2. ์ ์์ด ๋์ง ์์ผ๋ฏ๋ก ์ ์์ ์ฌ๋ ๊ฝ๋ค์ ์๋ฅผ ๊ฐ๋ฅํ ์ ๊ฒ ํ๋ค.
N๊ฐ์ ๊ฝ๋ค ์ค์์ ์์ ๋ ์กฐ๊ฑด์ ๋ง์กฑํ๋, ์ฆ 3์ 1์ผ๋ถํฐ 11์ 30์ผ๊น์ง ๋งค์ผ ๊ฝ์ด ํ ๊ฐ์ง ์ด์ ํผ์ด ์๋๋ก ๊ฝ๋ค์ ์ ํํ ๋, ์ ํํ ๊ฝ๋ค์ ์ต์ ๊ฐ์๋ฅผ ์ถ๋ ฅํ๋ ํ๋ก๊ทธ๋จ์ ์์ฑํ์์ค.
์
๋ ฅ๊ฐ์ (ํผ๋ ์, ํผ๋ ์ผ, ์ง๋ ์, ์ง๋ ์ผ)ํํ๋ก ์ฃผ์ด์ง๋ค.
3์ 1์ผ๋ถํฐ 11์ 30์ผ๊น์ง ๊ฝ์ด ๋งค์ผ ์ต์ ํ๊ฐ์ง๋ ํผ์ด์๋๋ก ์ ํํด์ผํ๋ค.
์ฃผ์ํด์ผ ํ ์ ์ ์ง๋ ๋ ์ง๊ฐ 5์ 10์ผ์ด๋ฉด ์ค์ ๋ก 5์ 9์ผ๋ ๊น์ง๋ง ํผ์ด์๋ค๋ ๋ป์ด๋ฏ๋ก ๋ง์ง๋ง ๊ฝ์ด ์ง๋ ๋ ์ง๋ ์ต์ 12์ 1์ผ์ด์ด์ผํ๋ค.
์ฌ์ค ๋์
๋๋ฆฌ๋ก ์ด์ฌํ ๋๋ค๊ฒจ๋ณด๋ค ๋งํ์ ํ์ด๋ฅผ ์ฐพ์๋ดค๋ค...
๋๋ถ๋ถ์ (ํผ๋ ์ * 100) + ํผ๋ ์ผ, (์ง๋ ์ * 100) + ์ง๋ ์ผ๋ก ๋ณํํด์ ํ๋๋ฐ ๊ตณ์ด ๊ทธ๋ ๊ฒ ํ ํ์๋ ์์๊ฒ๊ฐ๋ค.
๋จผ์ ์
๋ ฅ๊ฐ๋ค์ ์ค๋ฆ์ฐจ์์ผ๋ก ์ ๋ ฌํด์ค๋ค. (์ฐ์ ์์์ ์ธ์ ์์๊ฐ ๊ฐ๊ธฐ๋๋ฌธ์ key๊ฐ์ ๋ฐ๋ก ํ์์๋ค.)
๊ทธ๋ฌ๋ฉด ๊ฝ์ด ๋นจ๋ฆฌ ํผ๊ณ ์ง๋ ์์ผ๋ก ์ ๋ ฌ๋๋๋ฐ, ์ฐจ๋ก๋๋ก ํ์์ ์์ํ๋ค.
๊ฝ์ด ํ๋ฃจ๋ ๋น ์ง์์ด ํผ์ด์๊ฒ ํ๋ ค๋ฉด ์ด๋ป๊ฒ ํด์ผํ ๊น?
๋ง์ง๋ง ๊ฝ์ด ์ง๋ ๋ ์ง๋ฅผ ๊ธฐ์ค์ผ๋ก ์๋ก ์ฌ๋ ๊ฝ์ ํผ๋๋ ์ด ๋น ๋ฅด๊ฑฐ๋ ๊ฐ๊ณ , ์ง๋๋ ์ ๋๋ ค์ผํ๋ค.
์ ๊ฐ์ ๊ฒฝ์ฐ๋ ๋ฐ์ ธ์ผํ๋๋ฉด ์ค์ง์ ์ผ๋ก ๊ฝ์ด ํผ์ด์๋ ๊ธฐ๊ฐ์ (์ง๋๋ - 1)์ด๊ธฐ ๋๋ฌธ์ด๋ค.
์๋ฅผ๋ค์ด ๋ง์ง๋ง ๊ฝ์ ์ง๋๋ ์ด (4, 7)์ด๊ณ , ์๋ก์ด ๊ฝ์ ํผ๋๋ ์ด (4, 8)์ด๋ผ๋ฉด 4์ 7์ผ์๋ ์๋ฌด๋ฐ ๊ฝ๋ ์กด์ฌํ์ง ์๋๋ค.
๋ฐ๋ผ์ 1) ๋ง์ง๋ง ๊ฝ์ด ์ง๋๋ ์ง, 2) ๋ง์ง๋ง ๊ฝ์ ์ธ๋ฑ์ค๋ฒํธ, 3) ์ ํํ ๊ฝ์ ๊ฐฏ์ ๋ฅผ ์ ์ฅํด๊ฐ๋ฉฐ ํ์ํด์ผํ๋ค.
๋ฌธ์ ์กฐ๊ฑด์ ๋ณด๋ฉด 3์ 1์ผ๋ถํฐ ๊ฝ์ด ํผ์ด์์ด์ผ ํ๋ฏ๋ก (1)์ ์ด๊ธฐ๊ฐ์ (3, 1)๋ก ์ ์ฅ ํ ์์ํ๋ค.
๊ฝ์ ์ ๋ ฌ๋ ์์๋๋ก ํ์ํ๋ฉฐ ์ ์กฐ๊ฑด ์๋ก์ด ๊ฝ์ด ํผ๋๋ <= (m, d) < ์๋ก์ด ๊ฝ์ด ์ง๋๋ ์ ๋ง์กฑํ๋ค๋ฉด "์ฌ์ ์ ์๋ ๊ฝ ์ค ๊ฐ์ฅ ํจ์จ์ ์ธ ๊ฝ"์ ํ์ํ๋ค.
์ฆ, ์กฐ๊ฑด์ ๋ง์กฑํ๋ ๊ฝ ์ค ๊ฐ์ฅ ๋ฆ๊ฒ ์ง๋ ๊ฝ์ ์ฐพ๋๊ฒ์ด๋ค.
๋งค ๊ฝ๋ง๋ค ์๋์ ์กฐ๊ฑด์ ํ์ธ ํ ๊ฐ์ฅ ๋ฆ๊ฒ ์ง๋ ๋ latest๋ฅผ ์
๋ฐ์ดํธํ๋ค.
์กฐ๊ฑด์ ๋ง์กฑํ๋ฉด์ latest๋ณด๋ค ์ง๋ ๋ ์ง๊ฐ ๋ฆ๋ค๋ฉด latest๋ฅผ ์
๋ฐ์ดํธํด์ฃผ๊ณ , ๊ฝ์ด ํผ๋ ๋ ์ง๊ฐ (m, d)๋ณด๋ค ๋ฆ๋ค๋ฉด ๋ ์ด์์ ํ์์ ๋ฌด์๋ฏธํ๋ฏ๋ก ์ข
๋ฃํ๋ค.
๋ ์ด์ ๋ง์กฑํ๋ ๊ฝ์ด ์๋ค๋ฉด ๋ง์ง๋ง ๊ฝ์ด ์ง๋๋ ์ latest๋ก ์
๋ฐ์ดํธ ํ latest์ ๋ค์ ๊ฝ๋ถํฐ ๋ค์ ํ์์ ์์ํ๋ค.
ํ์ ์ค ๋ง์ง๋ง ๊ฝ์ด ์ง๋๋ ์ด 11์ 30์ผ๋ณด๋ค ์ปค์ง๋ฉด ํ์ ์ข
๋ฃ ํ ์ง๊ธ๊น์ง ์ ํํ ๊ฝ์ ๊ฐฏ์๋ฅผ ์ถ๋ ฅํ๋ค.
๋ง์ฝ ๋ชจ๋ ๊ฝ์ ์ฒดํฌํ์์๋ (3์ 1์ผ ~ 11์ 30)์ ๋ง์กฑํ ์ ์๋ค๋ฉด 0์ ์ถ๋ ฅํ๋ค.
์ฐธ๊ณ ๋ก Python์ while~else๋ ์ฌ์ฉํ ์ ์๋๋ฐ, while๋ฌธ์ break์์ด ๋ง์ณค๋ค๋ฉด else๋ฌธ์ด ์คํ๋๋ ๊ตฌ์กฐ๋ค. ์์ฃผ ์ข๋ค...
์ ์ฒด ์ฝ๋
# ๋ฉ๋ชจ๋ฆฌ: 41384KB / ์๊ฐ: 224ms
from sys import stdin
input = stdin.readline
N = int(input())
flowers = sorted(tuple(map(int, input().split())) for _ in range(N))
ret = 0
# ๊ฝ์ด ์ง๋ ๋ ์ง (์ด๊ธฐ๊ฐ: 3์ 1์ผ)
end = (3, 1)
i = 0
while i < N:
m1, d1, m2, d2 = flowers[i]
latest = 0
# ํ์ฌ ๊ฝ์ด ํผ๋๋ <= end < ์ง๋๋ ์ด๋ฉด ํ์ฌ ๊ฝ์ ์ฌ์ ์ ์์.
if (m1, d1) <= end < (m2, d2):
latest = (m2, d2)
# ์ ์กฐ๊ฑดํ์ ๊ฐ์ฅ ๋ฆ๊ฒ ์ง๋ ๊ฝ์ ์ฐพ๊ธฐ
while i < N-1:
m1, d1, m2, d2 = flowers[i+1]
if (m1, d1) > end: # ๊ฝ์ด ํผ๋๋ ์ง๊ฐ end๋ณด๋ค ๋ฆ๋ค๋ฉด ํ์ ์ข
๋ฃ
break
if (m2, d2) > latest:
latest = (m2, d2)
i += 1
end = latest
ret += 1
# ๊ฝ์ด ์ง๋ ๋ ์ง๊ฐ 11์ 30์ผ๋ณด๋ค ๋ฆ๋ค๋ฉด ์ถ๋ ฅ ํ ์ข
๋ฃ. (์ค์ ๊ฝ์ด ์ง๋๋ ์ (์ง๋๋ - 1)์ด๊ธฐ ๋๋ฌธ์ ๊ฐ๊ฑฐ๋ ์์ผ๋ฉด ์๋จ.)
if latest > (11, 30):
print(ret)
break
i += 1
else:
# break์์ด ๋น ์ ธ๋์ฌ๊ฒฝ์ฐ (๊ฝ์ด ์ง๋ ๋ ์ง๊ฐ 11์ 30์ผ์ ๋ชป๋๊ธธ๊ฒฝ์ฐ)
print(0)