๐Ÿ“ BOJ - ์ „๊นƒ์ค„

๋ฌธ์ œ

BOJ 2565๋ฒˆ : ์ „๊นƒ์ค„

์ ‘๊ทผ ๋ฐฉ๋ฒ•

์กฐํ•ฉ์„ ๊ตฌํ•ด์•ผํ•˜๋Š” ๋ฌธ์ œ์ฒ˜๋Ÿผ ๋ณด์ด์ง€๋งŒ ์ฆ๊ฐ€ํ•˜๋Š” ๊ฐ€์žฅ ๊ธด ์ˆ˜์—ด์„ ๊ตฌํ•˜๋Š” ๋ฌธ์ œ์ด๋‹ค!

์„ค๋ช…

๋ฌธ์ œ์˜ ์˜ˆ์‹œ๋ฅผ ๊ฐ€์ง€๊ณ  ์ƒ๊ฐํ•ด๋ณด์ž. ์„œ๋กœ ์—ฐ๊ฒฐ๋˜์–ด ์žˆ๋Š” ์ „๋ด‡๋Œ€A์™€ ์ „๋ด‡๋Œ€B์˜ ์œ„์น˜ ์Œ์€ [(1, 8), (3, 9), ... ]์œผ๋กœ ๋‚˜ํƒ€๋‚ผ ์ˆ˜ ์žˆ๋‹ค. ํ•˜์ง€๋งŒ ์ž…๋ ฅ๋œ ์œ„์น˜ ์Œ์ด ์ •๋ ฌ๋˜์–ด ์žˆ์ง€ ์•Š์œผ๋ฏ€๋กœ sort()๋ฅผ ์‚ฌ์šฉํ•ด ์ •๋ ฌํ•ด์ค€๋‹ค. ์ฐธ๊ณ ๋กœ ํŠœํ”Œ ์ •๋ ฌ์˜ ๊ฒฝ์šฐ ๊ฐ€์žฅ ์•ž์˜ ์š”์†Œ๋ฅผ ๊ธฐ์ค€์œผ๋กœ ์ •๋ ฌํ•œ๋‹ค.

์ด ๋•Œ์˜ ์ „๋ด‡๋Œ€B์˜ ์œ„์น˜๋ฅผ ๋‚˜์—ดํ•˜๋ฉด [8, 2, 9, 1, 4, 6, 7, 10]์ด๋‹ค. ์ด ๋ฆฌ์ŠคํŠธ์—์„œ ์ฆ๊ฐ€ํ•˜๋Š” ๊ฐ€์žฅ ๊ธด ๋ถ€๋ถ„ ์ˆ˜์—ด(Longest Increasing Subsequence)์„ ๊ตฌํ•˜๋ฉด ์ „๊นƒ์ค„์ด ์„œ๋กœ ๊ฒน์น˜์ง€ ์•Š๊ณ  ์—ฐ๊ฒฐ๋˜๊ฒŒ ๋œ๋‹ค. ์˜ˆ๋ฅผ ๋“ค๋ฉด ์ „๋ด‡๋Œ€ ์Œ (1, 8)๊ณผ (2, 2)์˜ ๊ฒฝ์šฐ ์ฆ๊ฐ€ํ•˜์ง€ ์•Š๋Š”๋ฐ ์ด ๊ฒฝ์šฐ ์ „๊นƒ์ค„์ด ๊ฒน์น˜๊ฒŒ ๋œ๋‹ค. ๋ฐ˜๋ฉด (2, 2), (6, 4), (10, 10)์˜ ๊ฒฝ์šฐ ์ฆ๊ฐ€ํ•˜๋Š” ์ˆ˜์—ด์ด๋ฏ€๋กœ ์ „๊นƒ์ค„์ด ๊ฒน์น˜์ง€ ์•Š๋Š”๋‹ค.

๊ฒฐ๋ก 

์ „๋ด‡๋Œ€ ์Œ์„ ์ •๋ ฌํ•œ ๋‹ค์Œ ์ „๋ด‡๋Œ€B์˜ ์œ„์น˜ ๋ฆฌ์ŠคํŠธ๋ฅผ ๊ฐ€์ง€๊ณ  ์ฆ๊ฐ€ํ•˜๋Š” ๊ฐ€์žฅ ๊ธด ๋ถ€๋ถ„ ์ˆ˜์—ด์„ ๊ตฌํ•˜์—ฌ, ๊ฒน์น˜์ง€ ์•Š๊ณ  ์—ฐ๊ฒฐํ•  ์ˆ˜ ์žˆ๋Š” ์ตœ๋Œ€ ์ „๊นƒ์ค„ ์ˆ˜๋ฅผ ๊ตฌํ•œ๋‹ค. ์ด๋ ‡๊ฒŒ ๊ตฌํ•œ ์ตœ๋Œ€๊ฐ’์„ NN์—์„œ ๋นผ์ฃผ๋ฉด ์ „๊นƒ์ค„์˜ ์ตœ์†Œ ๊ฐœ์ˆ˜๋ฅผ ๊ตฌํ•  ์ˆ˜ ์žˆ๋‹ค.

๊ตํ›ˆ

๊ฐ€์žฅ ๊ธด ์ฆ๊ฐ€ํ•˜๋Š” ๋ถ€๋ถ„ ์ˆ˜์—ด, ๊ฐ€์žฅ ๊ธด ๋ฐ”์ดํ† ๋‹‰ ๋ถ€๋ถ„ ์ˆ˜์—ด ๋“ฑ ์ˆ˜์—ด ๋ฌธ์ œ๋ฅผ ๋ชจ๋‘ ๋ชจ์•„์„œ ์ •๋ฆฌํ•ด์•ผ๊ฒ ๋‹ค.

์†Œ์Šค ์ฝ”๋“œ

n = int(input())
lines = [(0, 0)]
for _ in range(n):
  a, b = map(int, input().split())
  lines.append((a, b))
lines.sort()

table = [0] + [1]*n
for i in range(1, n+1):
  for j in range(i):
    if lines[i][1] > lines[j][1]:
        # ์•„๋ž˜ 2๊ฐœ์˜ ์ˆ˜ ์ค‘ ์ตœ๋Œ€๊ฐ’์œผ๋กœ table[i]๋ฅผ ๊ฐฑ์‹ ํ•œ๋‹ค.
        # 1. ๊ทธ ์ „ ์ˆซ์ž j๋กœ ์ธํ•ด ๊ฐฑ์‹ ๋œ table[i]
        # 2. ํ˜„์žฌ ์ˆซ์ž j๋กœ ์ธํ•ด ๊ฐฑ์‹ ๋  table[j]+1
        table[i] = max(table[i], table[j]+1)

print(n - max(table))

Written by@์ฝ”๋”ฉํ•˜๋Š”ํŽญ๊ท„
์ง€๊ธˆ์€ ํ•˜๊ณ  ์‹ถ์„ ๋•Œ๋งŒ ๊ณต๋ถ€ํ•ฉ๋‹ˆ๋‹ค๐Ÿค—

GitHubInstagramAI Notebook