๋ฐฑ์ค 9095 ํ์ด์ฌ
https://www.acmicpc.net/problem/9095
์ ์ n์ด ์ฃผ์ด์ก์ ๋, n์ 1,2,3์ ํฉ์ผ๋ก ๋ํ๋ด๋ ๋ฐฉ๋ฒ์ ์๋ฅผ ๊ตฌํ๋ ์๊ณ ๋ฆฌ์ฆ ๋ฌธ์ ์ ๋๋ค. ๋จ, ์์น์ ์ค๋ณต๊น์ง ๊ฐ๋ฅํ ์กฐ๊ฑด์ ๋๋ค.
์๋ฅผ ๋ค์ด 4๋ผ๋ ์ ์๋ฅผ ๋ง๋ค ๋
- 1+1+1+1
- 1+1+2
- 1+2+1
- 2+1+1
- 2+2
- 1+3
- 3+1
์ด๋ ๊ฒ ์์น์ ์ค๋ณต๊น์ง ๊ฐ๋ฅํ ์กฐ๊ฑด ์ ๋๋ค.
์ด ๋ฌธ์ ๋ ๋์ ๊ณํ๋ฒ์ ๊ณต๋ถํ๊ธฐ ์ํด ํ์ ๋ฌธ์ ์ธ๋ฐ์... ๋ฌธ์ ๋ฅผ ํด๊ฒฐํ๋ ๋ฐฉ๋ฒ์ ๊ณ ๋ฏผํด ๋ณด๋ฉด์ DFS๋ฅผ ์ฌ์ฉํ๊ณ ์ถ๋ค๋ ์๊ฐ์ด ๋ง์ด ๋ค์์ด์. ์์ด์ด๋ ์กฐํฉ์ ๊ตฌํ ๋ DFS๋ฅผ ์ฌ์ฉํด์ ํ๋ ๊ธฐ์ต์ด ์์ด์ ๋จผ์ ๋ ์ฌ๋๋๋ฐ์... ๋๊ฐ์ง ๋ฐฉ๋ฒ ๋ชจ๋ ์๋์ ์๋ฆฌ๋ฅผ ์ฌ์ฉํ์ต๋๋ค.
- ์ ์ n์ด ๋๊ธฐ ์ํด (1,2,3)์ ๋ํ ํฉ์ ๋ฐฉ๋ฒ์... (1,2,3)์ ๊ฐ๊ฐ ๋บ n-(1,2,3)์ ๋ํฉ ํฉ์ ๋ฐฉ๋ฒ์ ์ ๋ถ ํฉ์ฐํ ๊ฐ์ด๋ค
๊ธ๋ก ์ค๋ช ํ๊ธฐ์๋ ํ๋๋ ์๋ ํ๋ฅผ ๋ณด๋ฉด ์ดํด๊ฐ ๋ ๊ฒ์ด๋ค.
1 | 2 | 3 | 4 |
1 | (1) + 1 2 |
(1) + 2 (1 + 1) + 1 (2) + 1 3 |
-3 ์์น์์ ํฉ (1) + 3 -2 ์์น์์ ํฉ (1 + 1) + 2 (2) + 2 -1 ์์น์์ ํฉ (1 + 2) + 1 (1 + 1 + 1) + 1 (2 + 1) + 1 (3) + 1 |
ํผ๋ณด๋์น ์์ด์ธ๋ฐ 3๊ฐ์ฉ ๋ํ๋ ํ์์ ๋๋ค.
Python ํ์ด 1
๋จผ์ ๋์ ๊ณํ๋ฒ์ผ๋ก ๋ฌธ์ ๋ฅผ ํด๊ฒฐํ ํ์ด ์ ๋๋ค.
import sys
read = sys.stdin.readline
cache = [0] * 11
cache[1] = 1
cache[2] = 2
cache[3] = 4
for i in range(4, 11):
cache[i] = sum(cache[i-3:i])
T = int(read())
for _ in range(T):
print(cache[int(read())])
- ์ด๊ธฐ๊ฐ์ 1,2,3์ ๊ฒฝ์ฐ๊น์ง ๋จผ์ ์บ์๊ฐ์ ๋ฃ์ด์ค๋๋ค.
- ๋ฒ์๊ฐ 10๊น์ง ์ด๊ธฐ ๋๋ฌธ์ ๋ฏธ๋ฆฌ ๊ฐ๋ค์ ๋ชจ๋ ๊ตฌํ๊ณ ๋ฆฌ์คํธ๋ฅผ ์ํํ๋๋ก ํฉ๋๋ค.
- i ๋ถํฐ ์ด์ 3๊ฐ๊น์ง ํฉ์ฐ์ ๊ตฌํ๋ค.
Python ํ์ด 2
์ด๋ฒ ํ์ด๋ DFS๋ฅผ ์ด์ฉํ ํ์ด์ ๋๋ค.
import sys
read = sys.stdin.readline
def dfs(num):
if arr[num] > 0:
return arr[num]
if num == 1:
return 1
elif num == 2:
return 2
elif num == 3:
return 4
else:
arr[num] = dfs(num-1) + dfs(num-2) + dfs(num-3)
return arr[num]
T = int(sys.stdin.readline())
for _ in range(T):
l = int(read())
arr = [0] * (l+1)
print(dfs(l))
- ๋์ ๊ณํ๋ฒ์ด๋ ์๋ฆฌ๋ ๊ฐ์ต๋๋ค. ๋จ ์ฌ๊ท๋ฅผ ํตํด์ ๊ตฌํ๋ ์ฐจ์ด๋ง ์์ต๋๋ค.
๋ฏธ๋ฆฌ ๊ฐ๋ค์ด ๋ค์ด ์๋ ๋ฐฐ์ด์ ๋ง๋ค์ด์ ํด๋๋๋๋ฐ... ๊ทธ๋ด๋ ค๋ฉด 1,2,3์ ๋ํ ์ด๊ธฐ๊ฐ์ ๋ฐฐ์ด์ ์ง์ ๋ฃ์ด ๋์ ๊ณํ๋ฒ์ด๋ ๋๋ฌด ๊ฐ์ ๊ฒ ๊ฐ์์ ๋งค๋ฒ ๋ค์ ์ํํ๋ ํ์์ผ๋ก ํ์์ต๋๋ค.
๋๊ธ