๋ณธ๋ฌธ ๋ฐ”๋กœ๊ฐ€๊ธฐ
Coding Test/Algorithms

[Baekjoon] 2565.์ „๊นƒ์ค„/Python - Gold5

by The Future Engineer, Lucy 2024. 11. 5.
728x90
๋ฐ˜์‘ํ˜•

โ“๋ฌธ์ œ

https://www.acmicpc.net/problem/2565

์„ฑ๋Šฅ ์š”์•ฝ

๋ฉ”๋ชจ๋ฆฌ: 109240 KB, ์‹œ๊ฐ„: 92 ms

๋ฌธ์ œ ์„ค๋ช…

๋‘ ์ „๋ด‡๋Œ€ A์™€ B ์‚ฌ์ด์— ํ•˜๋‚˜ ๋‘˜์”ฉ ์ „๊นƒ์ค„์„ ์ถ”๊ฐ€ํ•˜๋‹ค ๋ณด๋‹ˆ ์ „๊นƒ์ค„์ด ์„œ๋กœ ๊ต์ฐจํ•˜๋Š” ๊ฒฝ์šฐ๊ฐ€ ๋ฐœ์ƒํ•˜์˜€๋‹ค. ํ•ฉ์„ ์˜ ์œ„ํ—˜์ด ์žˆ์–ด ์ด๋“ค ์ค‘ ๋ช‡ ๊ฐœ์˜ ์ „๊นƒ์ค„์„ ์—†์•  ์ „๊นƒ์ค„์ด ๊ต์ฐจํ•˜์ง€ ์•Š๋„๋ก ๋งŒ๋“ค๋ ค๊ณ  ํ•œ๋‹ค.

์˜ˆ๋ฅผ ๋“ค์–ด, < ๊ทธ๋ฆผ 1 >๊ณผ ๊ฐ™์ด ์ „๊นƒ์ค„์ด ์—ฐ๊ฒฐ๋˜์–ด ์žˆ๋Š” ๊ฒฝ์šฐ A์˜ 1๋ฒˆ ์œ„์น˜์™€ B์˜ 8๋ฒˆ ์œ„์น˜๋ฅผ ์ž‡๋Š” ์ „๊นƒ์ค„, A์˜ 3๋ฒˆ ์œ„์น˜์™€ B์˜ 9๋ฒˆ ์œ„์น˜๋ฅผ ์ž‡๋Š” ์ „๊นƒ์ค„, A์˜ 4๋ฒˆ ์œ„์น˜์™€ B์˜ 1๋ฒˆ ์œ„์น˜๋ฅผ ์ž‡๋Š” ์ „๊นƒ์ค„์„ ์—†์• ๋ฉด ๋‚จ์•„์žˆ๋Š” ๋ชจ๋“  ์ „๊นƒ์ค„์ด ์„œ๋กœ ๊ต์ฐจํ•˜์ง€ ์•Š๊ฒŒ ๋œ๋‹ค.

< ๊ทธ๋ฆผ 1 >

์ „๊นƒ์ค„์ด ์ „๋ด‡๋Œ€์— ์—ฐ๊ฒฐ๋˜๋Š” ์œ„์น˜๋Š” ์ „๋ด‡๋Œ€ ์œ„์—์„œ๋ถ€ํ„ฐ ์ฐจ๋ก€๋Œ€๋กœ ๋ฒˆํ˜ธ๊ฐ€ ๋งค๊ฒจ์ง„๋‹ค. ์ „๊นƒ์ค„์˜ ๊ฐœ์ˆ˜์™€ ์ „๊นƒ์ค„๋“ค์ด ๋‘ ์ „๋ด‡๋Œ€์— ์—ฐ๊ฒฐ๋˜๋Š” ์œ„์น˜์˜ ๋ฒˆํ˜ธ๊ฐ€ ์ฃผ์–ด์งˆ ๋•Œ, ๋‚จ์•„์žˆ๋Š” ๋ชจ๋“  ์ „๊นƒ์ค„์ด ์„œ๋กœ ๊ต์ฐจํ•˜์ง€ ์•Š๊ฒŒ ํ•˜๊ธฐ ์œ„ํ•ด ์—†์• ์•ผ ํ•˜๋Š” ์ „๊นƒ์ค„์˜ ์ตœ์†Œ ๊ฐœ์ˆ˜๋ฅผ ๊ตฌํ•˜๋Š” ํ”„๋กœ๊ทธ๋žจ์„ ์ž‘์„ฑํ•˜์‹œ์˜ค.

โœ๐Ÿปํ’€์ด

DP ๋ฌธ์ œ์ด๋‹ค.
๊ทธ๋ฆผ์„ ๋ดค์„ ๋•Œ, ์šฐ์„  A๋ฅผ ๊ธฐ์ค€์œผ๋กœ ์ •๋ ฌํ•˜๋Š” ๊ฒƒ์ด ์ข‹๊ฒ ๋‹ค๊ณ  ์ƒ๊ฐํ–ˆ๋‹ค.
๊ทธ๋ฆฌ๊ณ  ๊ต์ฐจํ•˜์ง€ ์•Š๋Š” ๊ฒฝ์šฐ๋ฅผ ์ƒ๊ฐํ–ˆ๋‹ค. B๊ฐ€ ์ด์ „ ์ „๊นƒ์ค„๋ณด๋‹ค ํฌ๋‹ค๋ฉด ๊ฒน์น˜์ง€ ์•Š๋Š”๋‹ค.
์ฆ‰, (3, 3)์˜ ๊ฒฝ์šฐ (1, 8), (2, 2)๋Š” ๊ฒน์น˜์ง€ ์•Š๋Š”๋‹ค.
์ „์ฒด ์ „๊นƒ์ค„์—์„œ ๊ฒน์น˜์ง€ ์•Š๋Š” ์ „๊นƒ์ค„์˜ ์ตœ๋Œ“๊ฐ’์„ ๋นผ๋ฉด ๊ทธ๊ฒƒ์ด ์—†์• ์•ผ ํ•˜๋Š” ์ตœ์†Œ์˜ ์ „๊นƒ์ค„์˜ ๊ฐœ์ˆ˜๊ฐ€ ๋œ๋‹ค.

๐Ÿ’ป์ฝ”๋“œ

import sys

input = sys.stdin.readline

n = int(input())
wires = [list(map(int, input().split())) for _ in range(n)]
wires.sort()
dp = [1] * n

for i in range(n):
    for j in range(i):
        if wires[i][1] > wires[j][1]:
            dp[i] = max(dp[j] + 1, dp[i])

print(n - max(dp))

๐Ÿ“ํ›„๊ธฐ

DP๋ผ๋Š” ๊ฑธ ์•Œ์•„๋„ Memorization์„ ์–ด๋–ป๊ฒŒ ์จ์•ผํ• ์ง€ ์ž˜ ์ƒ๊ฐ๋‚˜์ง€ ์•Š๋Š”๋‹ค.

728x90
๋ฐ˜์‘ํ˜•