CodingTest/Python
BOJ_9461 : ํ๋๋ฐ ์์ด
Soom_1n
2022. 9. 3. 02:40
9461๋ฒ: ํ๋๋ฐ ์์ด
์ค๋ฅธ์ชฝ ๊ทธ๋ฆผ๊ณผ ๊ฐ์ด ์ผ๊ฐํ์ด ๋์ ๋ชจ์์ผ๋ก ๋์ฌ์ ธ ์๋ค. ์ฒซ ์ผ๊ฐํ์ ์ ์ผ๊ฐํ์ผ๋ก ๋ณ์ ๊ธธ์ด๋ 1์ด๋ค. ๊ทธ ๋ค์์๋ ๋ค์๊ณผ ๊ฐ์ ๊ณผ์ ์ผ๋ก ์ ์ผ๊ฐํ์ ๊ณ์ ์ถ๊ฐํ๋ค. ๋์ ์์ ๊ฐ์ฅ ๊ธด ๋ณ์
www.acmicpc.net
๐ธ ๋ฌธ์ ๋ถ์ ๐ธ
- ๊ท์น์ฒ๋ผ ํ์ค๋ฆฌ ๋ชจ์์ผ๋ก ์ผ๊ฐํ์ด ๋์ด๊ฐ๋ ๊ฐ์ฅ ํฐ ๋ณ์ ๊ธธ์ด๋ฅผ ์ถ๋ ฅํ๋ ๋ฌธ์ ์ด๋ค.
- dp[0] ~ dp[9] ๊น์ง์ 10๊ฐ ๊ฐ์ ๋ฌธ์ ์์ ์ฃผ์ด์ก๋ค.
- ์ธ๋ฑ์ค 3(์
๋ ฅ ๊ฐ 4)๋ถํฐ ์ ํ์์ด ์ ์ฉ๋๋ค.
- P(N) = P(N-2) + P(N-3)
๐ธ ์ฝ๋ ๐ธ
dp = [1,1,1,2,2,3,4,5,7,9]
for _ in range(int(input())):
n = int(input())
if n <= len(dp):
print(dp[n-1])
else:
for _ in range(n-len(dp)):
dp.append(dp[-2]+dp[-3])
print(dp[n-1])
๐ธ ์ฝ๋ ํด์ ๐ธ
- dp ๋ฆฌ์คํธ์ ๋ฌธ์ ์์ ์ฃผ์ด์ง 10๊ฐ์ ๊ฐ์ ์ ์ฅํ๊ณ ์์ํ๋ค.
- ์ฃผ์ด์ง ๊ฐ(n)์ด dp ๋ฆฌ์คํธ์ ํฌ๊ธฐ๋ณด๋ค ํฌ๋ค๋ฉด(์๋ ์ธ๋ฑ์ค๋ผ๋ฉด), ๊ทธ ์ฐจ์ด๋งํผ ๊ณ์ฐํด์ dp ๋ฆฌ์คํธ๋ฅผ ๋๋ ค์ค๋ค.
- ํด๋น dp ๋ฆฌ์คํธ ์ธ๋ฑ์ค ๊ฐ์ ์ถ๋ ฅํ๋ค.
๐ธ end ๐ธ
- ๋ต์์ ์ฐพ์๋ณด์ง ์๊ณ ํ์ดํ๊ฑฐ๋ผ ์ํ์ ์๋ฆฌ๋ฅผ ์ค๋ช ํ๊ธฐ๊ฐ ์ข ์ด๋ ค์ด ๊ฒ ๊ฐ๋ค.
- ๊ทธ๋ฅ ๊ท์น์ฐพ๊ธฐ๊ฐ์ ๋ฌธ์ ์๋๋ฐ dp ๋ฌธ์ ๋ค์ ๊ฐ๋จํ ํ์๋ ์ด๋ฐ ๋ฐฉ๋ฒ๋ ์์ฃผ ์ฌ์ฉ๋๋ ๊ฒ ๊ฐ๋ค.
- dp ๋ฆฌ์คํธ ์ถ๋ ฅ์ ์ธ๋ฑ์ค๋ฅผ -1 ํด์ค์ผํ๋๋ฐ, ๊ทธ๊ฑธ ํ๋๋ง ๋ฐ๊ฟ์ค์ 1ํ ํ๋ ธ๋ค.
728x90