๋ฌธ์
https://www.acmicpc.net/problem/11053
11053๋ฒ: ๊ฐ์ฅ ๊ธด ์ฆ๊ฐํ๋ ๋ถ๋ถ ์์ด
์์ด A๊ฐ ์ฃผ์ด์ก์ ๋, ๊ฐ์ฅ ๊ธด ์ฆ๊ฐํ๋ ๋ถ๋ถ ์์ด์ ๊ตฌํ๋ ํ๋ก๊ทธ๋จ์ ์์ฑํ์์ค. ์๋ฅผ ๋ค์ด, ์์ด A = {10, 20, 10, 30, 20, 50} ์ธ ๊ฒฝ์ฐ์ ๊ฐ์ฅ ๊ธด ์ฆ๊ฐํ๋ ๋ถ๋ถ ์์ด์ A = {10, 20, 10, 30, 20, 50} ์ด
www.acmicpc.net
๋ด ๋ฌธ์ ํ์ด
n = int(input())
permu = list(map(int, input().split()))
count = [1] # ์ฒซ ๋ฒ์งธ ์ซ์์ ๊ธธ์ด๋ ์ด์ฐจํผ 1์ด๋ฏ๋ก ๋ฏธ๋ฆฌ ์ถ๊ฐ
counting = 0
def find(now):
global counting
for i in reversed(range(len(count))):
if counting < count[i] and permu[i] < now:
counting = count[i]
for i in range(1, n):
find(permu[i])
count.append(counting+1)
counting = 0
print(max(count))
๐ DP ๋ฌธ์ ๋ก, ๋๋ณด๋ค ์์ ๊ฐ์ฅ ๊ธด ์ฆ๊ฐํ๋ ์์ด์ ๋ํ ์นด์ดํธ๋ฅผ ๋์ ํ๋ ๊ฒ์ด ํฌ์ธํธ !
- ์ฃผ์ด์ง permu ๋ฆฌ์คํธ๋ฅผ ์์ฐจ์ ์ผ๋ก ๋๋ฉด์ find ํจ์๋ฅผ ์คํํด์ฃผ์๋ค.
find ํจ์๋ ํ์ฌ ์ซ์๋ฅผ ์ธ์๋ก ๋ฐ๋๋ฐ, ํ์ฌ ์ซ์ ์ด์ ์ ์ซ์๋ค์ ๊ฒ์ฌํ๋ฉด์,
ํ์ฌ ์ซ์๋ณด๋ค ์์ ์ ์ค์ count์ ์ ์ฅ๋ ๊ฐ์ด ๊ฐ์ฅ ํฐ ๊ฐ์ counting์ ์ ์ฅํ๋ค. - ๊ทธ๋ฆฌ๊ณ find์์ ๊ตฌํ counting์ 1์ ๋ํ ๊ฐ์ count ๋ฆฌ์คํธ์ ์ถ๊ฐํ๊ณ ,
๋ค์ ๋ฐ๋ณต์ด ์ํ๋๊ธฐ ์ counting ๋ณ์๋ ๋ค์ 0์ผ๋ก ์ด๊ธฐํํ๋ค. - ์ด๋ฌํ ์ํ์ ๋ฐ๋ณตํ์ฌ count์ ์ ์ฅ๋ ๊ฐ ์ค ๊ฐ์ฅ ํฐ ๊ฐ์ ์ถ๋ ฅํ๋ค.
โ ์ด ๋ฌธ์ ๋ ์์ฃผ ์ ํ์ ์ธ LIS ๋ฌธ์ ์ด๋ฏ๋ก, ๊ฐ์ด ๋ณด๋ฉด ์ข์ ๊ฒ ๊ฐ์ ์ถ๊ฐํ๋ค.
https://seolhee2750.tistory.com/109?category=872093
[Swift Algorithm Note] ์ต์ฅ ์ฆ๊ฐ ๋ถ๋ถ ์์ด (feat. DP)
์ค๋์ ์ต์ฅ ์ฆ๊ฐ ๋ถ๋ถ ์์ด (LIS)์ ๋ํด ์ ๋ฆฌํด๋ณด๋ คํ๋ค. LIS๋ฅผ ๊ตฌํ๋ ๋ฐฉ๋ฒ์ ์ฌ๋ฌ๊ฐ์ง์ง๋ง, ๊ทธ ์ค์์๋ ๊ฐ์ฅ ๊ฐํธํ DP๋ฅผ ์ด์ฉํ ๋ฐฉ๋ฒ์ ์๊ฐํ๋ค. (DP์ ๋ํด ๊ถ๊ธํ์ ๋ถ๋ค์ ์๊ธฐ๐๋ฅผ ์ฐธ๊ณ
seolhee2750.tistory.com
๐ก ํผ๋๋ฐฑ
- ์ฌ์ด ๋ฌธ์ ์ง๋ง, LIS ์ ํ์ ๋ชจ๋ฅธ๋ค๋ฉด ์๊ฐํ๊ธฐ ์ด๋ ค์ธ ์ ์๋ ๋ฌธ์ ๊ฐ๋ค.
๋๋ DP ์์ฒด๋ฅผ ์ค๋๋ง์ ํ์๋๋ ์๊ฐ์ด ์ข ๊ฑธ๋ ธ๋ค.
'4๏ธโฃ Python > Problem Solving' ์นดํ ๊ณ ๋ฆฌ์ ๋ค๋ฅธ ๊ธ
[Python Algorithm] ํฌ๋์ฃผ ์์ BOJ #2156 (0) | 2022.01.31 |
---|---|
[Python Algorithm] ์ฐ์ํฉ BOJ #1912 (0) | 2022.01.31 |
[Python Algorithm] ์ฌ์ ๊ฐ์ BOJ #4963 (0) | 2022.01.30 |
[Python Algorithm] ํ ๋งํ BOJ #7576 (0) | 2022.01.30 |
[Python Algorithm] ์ฐ๊ตฌ์ BOJ #14502 (0) | 2022.01.30 |
๋๊ธ