[ ๋ฌธ์ ]
https://www.acmicpc.net/problem/9095
9095๋ฒ: 1, 2, 3 ๋ํ๊ธฐ
๊ฐ ํ ์คํธ ์ผ์ด์ค๋ง๋ค, n์ 1, 2, 3์ ํฉ์ผ๋ก ๋ํ๋ด๋ ๋ฐฉ๋ฒ์ ์๋ฅผ ์ถ๋ ฅํ๋ค.
www.acmicpc.net
[ ๋์ ํ์ด ]
๐ธ ์ ๊ทผ ๋ฐฉ๋ฒ
์ฃผ์ด์ง ์ซ์๋ฅผ 1, 2, 3 ์ผ๋ก ๋นผ์ 0์ด ๋ ๋๊น์ง ๋บ๋ค. 0์ด ๋๋ ๊ฒฝ์ฐ์๋ return ํ๋ค.
1, 2, 3์ผ๋ก ๋บ๋ ๊ฐ์ ๋ฌธ์์ด๋ก ์ ์ฅํ๋ค. ๋ฌธ์์ด ๊ฐ์ answer๋ผ๋ list์ ์ ์ฅํ๋ค.
ํด๋น list์ ์กด์ฌํ์ง ์์ผ๋ฉด ๋ฌธ์์ด ๊ฐ์ ์ถ๊ฐํ๋ค.
list์ ๊ธธ์ด๊ฐ ๊ณง ํฉ์ ๋ํ๋ผ ์ ์๋ ๋ฐฉ๋ฒ์ ์๊ฐ ๋๋ค.
๐ธ ํ์ด ์ฝ๋
# n์ด 1, 2, 3์ ํฉ์ผ๋ก ๊ตฌ์ฑ๋์ด ์๋ ๊ฒฝ์ฐ๋ฅผ ์ฐพ๋ ํจ์
def find(n, string):
# n์ ๊ฐ์ด 0์ธ ๊ฒฝ์ฐ
if n == 0:
# ๊ทธ๋์ ๊ฐ์ ๋บ string์ด ์ ์ฅํ์ง ์์ ๊ฒฝ์ฐ์๋ง answer list์ ๊ฐ ์ ์ฅ
if not string in answer:
answer.append(string)
return
# n์ ๊ฐ์ด 0์ด ์๋ ๊ฒฝ์ฐ. 1, 2, 3 ์์๋๋ก ๋นผ๊ณ , ๋บ ์ซ์๋ฅผ ๋ฌธ์์ด๋ก ๊ธฐ๋ก
for num in [1, 2, 3]:
if n >= num:
find(n-num, string + str(num))
else:
continue
# ํ
์คํธ ์ผ์ด์ค ๊ฐ์ T
T = int(input())
# ํ
์คํธ ์งํํ๋ ๋ฐ๋ณต๋ฌธ
for _ in range(T):
# ๋บ ์ซ์๋ฅผ ์ ์ฅํ list
answer = list()
# ์ธํ ์ ์๊ฐ N
N = int(input())
# find ํจ์๋ฅผ ํตํด N๊ฐ์ด 1, 2, 3์ผ๋ก ์ด๋ฃจ์ด์ง ๊ฒฝ์ฐ๋ฅผ answer์ ์ ์ฅ
find(N, '')
# answer์ ๊ธธ์ด ์ถ๋ ฅ
print(len(answer))
[ pair์ ํ์ด ]
๐ธ ์ ๊ทผ ๋ฐฉ๋ฒ
pair๋ ํผ๋ณด๋์น ์์ด์ ๊ท์น์ด ์๋ค๋ ๊ฒ์ ์ฐพ์๋๋ค..... ์ด์ผ ํ์ง... ๐ฏ
๊ทธ ์ 3๊ฐ์ ํฉ์ด ๊ทธ ๋ค์ ์ ์์ ๊ฐ์ด ๋๋ค.
์ ์ฒด ์ ์๊ฐ 11๊น์ง์ฌ์ 11๊น์ง์ ํผ๋ณด๋์น ์์ด ๊ฐ์ ๋ค ์ ์ฅํด๋๊ณ ๊ฐ์ ์ถ๋ ฅํ๋ค.
์งฑ๐
๐ธ ํ์ด ์ฝ๋
t = int(input())
arr = [0 for _ in range(11)]
arr[1] = 1 # 1
arr[2] = 2 # 1+1, 2
arr[3] = 4 # 1+1+1, 1+2, 2+1, 3
for i in range(4, 11):
arr[i] = sum(arr[i-3:i])
for _ in range(t):
n = int(input())
print(arr[n])
pair ์ github : https://github.com/Ui-Seok
'๐ถ Programming > ์๊ณ ๋ฆฌ์ฆ ๋ฌธ์ ํ๊ธฐ' ์นดํ ๊ณ ๋ฆฌ์ ๋ค๋ฅธ ๊ธ
BOJ. 11723 ์งํฉ (Python) (0) | 2022.12.09 |
---|---|
BOJ. 7662 ์ด์ค ์ฐ์ ์์ ํ (Python) (4) | 2022.12.08 |
BOJ. 12100 2048 (Easy) (Python) (3) | 2022.10.07 |
BOJ. 1725 ํ์คํ ๊ทธ๋จ (Python) (0) | 2022.10.03 |
2021 ์นด์นด์ค ์ฑ์ฉ์ฐ๊ณํ ์ธํด์ญ Lv2. ๊ฑฐ๋ฆฌ๋๊ธฐ ํ์ธํ๊ธฐ (0) | 2022.09.11 |