๐ ์ถ์ฒ - 9095 - 1, 2, 3 ๋ํ๊ธฐ
๋ฌธ์ ์ค๋ช
์ ์ 4๋ฅผ 1, 2, 3์ ํฉ์ผ๋ก ๋ํ๋ด๋ ๋ฐฉ๋ฒ์ ์ด 7๊ฐ์ง๊ฐ ์๋ค. ํฉ์ ๋ํ๋ผ ๋๋ ์๋ฅผ 1๊ฐ ์ด์ ์ฌ์ฉํด์ผ ํ๋ค.
์ ์ n์ด ์ฃผ์ด์ก์ ๋, n์ 1, 2, 3์ ํฉ์ผ๋ก ๋ํ๋ด๋ ๋ฐฉ๋ฒ์ ์๋ฅผ ๊ตฌํ๋ ํ๋ก๊ทธ๋จ์ ์์ฑํ์์ค.
์
๋ ฅ
์ฒซ์งธ ์ค์ ํ
์คํธ ์ผ์ด์ค์ ๊ฐ์ T๊ฐ ์ฃผ์ด์ง๋ค. ๊ฐ ํ
์คํธ ์ผ์ด์ค๋ ํ ์ค๋ก ์ด๋ฃจ์ด์ ธ ์๊ณ , ์ ์ n์ด ์ฃผ์ด์ง๋ค. n์ ์์์ด๋ฉฐ 11๋ณด๋ค ์๋ค.
์ถ๋ ฅ
๊ฐ ํ
์คํธ ์ผ์ด์ค๋ง๋ค, n์ 1, 2, 3์ ํฉ์ผ๋ก ๋ํ๋ด๋ ๋ฐฉ๋ฒ์ ์๋ฅผ ์ถ๋ ฅํ๋ค.
์ ์ถ๋ ฅ ์
์์ ์ ๋ ฅ | ์์ ์ถ๋ ฅ |
---|---|
3 4 7 10 | 7 44 274 |
๋ค์ ๋ก์ง์ DP ์๊ณ ๋ฆฌ์ฆ์ ์ฌ์ฉํด ํด๊ฒฐํ๋ฉด ๊ฐ๋จํฉ๋๋ค.
DP ์๊ณ ๋ฆฌ์ฆ์ ๋ฏธ๋ฆฌ ๊ฐ์ ์ ์ฅํ ํ ๊ทธ ๊ฐ์ ์ด์ฉํด ์๊ฐ์ ๋จ์ถํ๋ ์๊ณ ๋ฆฌ์ฆ์ธ๋ฐ ๋ํ์ ์ผ๋ก๋ ํผ๋ณด๋์น ์๊ณ ๋ฆฌ์ฆ์ ๋น์ ํด ์ด์ผ๊ธฐ ํ ์ ์์ต๋๋ค.
index | value |
---|---|
1 | 1 |
2 | 2 |
3 | 4 |
4 | 7 |
5 | 13 |
6 | 24 |
7 | 44 |
7๋ฒ์งธ๊น์ง ๊ฐ์ ๊ตฌํด๋ณธ ํ์ ๋๋ค. ์ด๋ ๊ฒ ๋ณด๋ฉด ๊ท์น์ด ๋ค๋ค ๋ณด์ด์ค๊น์~?
Logic
index 1, 2, 3์ ๋ํ๋ฉด 4์ ๊ฐ์ด ๋์ค๊ณ , 5์ ๊ฐ์ 2, 3, 4์ ๊ฐ์ ๋ํด์ฃผ๋ฉด ๋ฉ๋๋ค.
result[i] = result[i-3] + result[i-2] + result[i-1]
import sys
input = sys.stdin.readline
T = int(input())
for i in range(T):
result = [1, 2, 4]
n = int(input())
if n <= 3:
print(result[n-1])
continue
for i in range(3, n):
result.append(result[i-3] + result[i-2] + result[i-1])
print(result[-1])