CS log
[๋ฐฑ์ค/python] 4779๋ฒ : ์นธํ ์ด ์งํฉ ๋ณธ๋ฌธ
๐๋ฌธ์
https://www.acmicpc.net/problem/4779
์นธํ ์ด ์งํฉ์ 0๊ณผ 1์ฌ์ด์ ์ค์๋ก ์ด๋ฃจ์ด์ง ์งํฉ์ผ๋ก, ๊ตฌ๊ฐ [0, 1]์์ ์์ํด์ ๊ฐ ๊ตฌ๊ฐ์ 3๋ฑ๋ถํ์ฌ ๊ฐ์ด๋ฐ ๊ตฌ๊ฐ์ ๋ฐ๋ณต์ ์ผ๋ก ์ ์ธํ๋ ๋ฐฉ์์ผ๋ก ๋ง๋ ๋ค. ์ ์ฒด ์งํฉ์ด ์ ํ์ด๋ผ๊ณ ๊ฐ์ ํ๊ณ , ๋ค์๊ณผ ๊ฐ์ ๊ณผ์ ์ ํตํด์ ์นธํ ์ด ์งํฉ์ ๊ทผ์ฌ๋ฅผ ๋ง๋ค์ด๋ณด์.
1. -๊ฐ 3N๊ฐ ์๋ ๋ฌธ์์ด์์ ์์ํ๋ค.
2. ๋ฌธ์์ด์ 3๋ฑ๋ถ ํ ๋ค, ๊ฐ์ด๋ฐ ๋ฌธ์์ด์ ๊ณต๋ฐฑ์ผ๋ก ๋ฐ๊พผ๋ค. ์ด๋ ๊ฒ ํ๋ฉด, ์ (๋ฌธ์์ด) 2๊ฐ๊ฐ ๋จ๋๋ค.
3. ์ด์ ๊ฐ ์ (๋ฌธ์์ด)์ 3๋ฑ๋ถ ํ๊ณ , ๊ฐ์ด๋ฐ ๋ฌธ์์ด์ ๊ณต๋ฐฑ์ผ๋ก ๋ฐ๊พผ๋ค. ์ด ๊ณผ์ ์ ๋ชจ๋ ์ ์ ๊ธธ์ด๊ฐ 1์ผ๋ ๊น์ง ๊ณ์ ํ๋ค.
์๋ฅผ ๋ค์ด, N=3์ธ ๊ฒฝ์ฐ, ๊ธธ์ด๊ฐ 27์ธ ๋ฌธ์์ด๋ก ์์ํ๋ค.
---------------------------
์ฌ๊ธฐ์ ๊ฐ์ด๋ฐ ๋ฌธ์์ด์ ๊ณต๋ฐฑ์ผ๋ก ๋ฐ๊พผ๋ค.
--------- ---------
๋จ์ ๋ ์ ์ ๊ฐ์ด๋ฐ ๋ฌธ์์ด์ ๊ณต๋ฐฑ์ผ๋ก ๋ฐ๊พผ๋ค.
--- --- --- ---
ํ๋ฒ ๋
- - - - - - - -
๋ชจ๋ ์ ์ ๊ธธ์ด๊ฐ 1์ด๋ฉด ๋ฉ์ถ๋ค. N์ด ์ฃผ์ด์ก์ ๋, ๋ง์ง๋ง ๊ณผ์ ์ด ๋๋ ํ ๊ฒฐ๊ณผ๋ฅผ ์ถ๋ ฅํ๋ ํ๋ก๊ทธ๋จ์ ์์ฑํ์์ค
๐์ ๋ ฅ
์ ๋ ฅ์ ์ฌ๋ฌ ์ค๋ก ์ด๋ฃจ์ด์ ธ ์๋ค. ๊ฐ ์ค์ N์ด ์ฃผ์ด์ง๋ค. ํ์ผ์ ๋์์ ์ ๋ ฅ์ ๋ฉ์ถ๋ค. N์ 0๋ณด๋ค ํฌ๊ฑฐ๋ ๊ฐ๊ณ , 12๋ณด๋ค ์๊ฑฐ๋ ๊ฐ์ ์ ์์ด๋ค.
๐์ถ๋ ฅ
์ ๋ ฅ์ผ๋ก ์ฃผ์ด์ง N์ ๋ํด์, ํด๋นํ๋ ์นธํ ์ด ์งํฉ์ ๊ทผ์ฌ๋ฅผ ์ถ๋ ฅํ๋ค.
๐ํ์ด ๋ฐฉ๋ฒ
- ๊ฐ์ด๋ฐ๋ฅผ ๋ฐ๋ณตํด์ ์๋ฅผ ์ ์์ ๋๊น์ง ์๋ผ์ค์ผ ํ๋, ์ฌ๊ท๋ฅผ ์ด์ฉํ์ฌ ํ์.
- "๊ฐ์ด๋ฐ"๋? 3**N ๊ฐ๋ฅผ 3๊ฐ๋ก ๋๋ ๊ฒ ์ค ๊ฐ์ด๋ฐ ์กฐ๊ฐ
- n๋ฒ์งธ ๊ฒฐ๊ณผ๋ n-1๋ฒ์งธ ๊ฒฐ๊ณผ๋ฅผ ์ด์ด๋ถ์ธ ๊ฒ๊ณผ ๊ฐ๋ค. n-1๋ฒ์งธ ๊ฒฐ๊ณผ ์ฌ์ด์ n-1๋ฒ์งธ ๊ฒฐ๊ณผ์ ๊ธธ์ด๋งํผ ๊ณต๋ฐฑ๋ง ๋ฃ์ด์ฃผ๋ฉด ๋๋ค. ์ฆ, n๋ฒ์งธ ๊ฒฐ๊ณผ = n-1๋ฒ์งธ ๊ฒฐ๊ณผ + n-1๋ฒ์งธ ๊ฒฐ๊ณผ ๊ธธ์ด๋งํผ์ ๊ณต๋ฐฑ + n-1๋ฒ์งธ ๊ฒฐ๊ณผ
๐์ฝ๋
import sys
def can(n) :
if n == 1 :
return "-"
cantor_unit = can(n//3)
cantor_res = cantor_unit + " " * (n//3) + cantor_unit
return cantor_res
while True :
try :
N = int(sys.stdin.readline())
print(can(3**N))
except :
break
๐์๊ฐ๋ณต์ก๋
O(3^N)
๐์ฌ๊ท
์ด ๋ถ๋ถ์ด ํต์ฌ ํฌ์ธํธ!
โก๏ธ n๋ฒ์งธ ๊ฒฐ๊ณผ๋ n-1๋ฒ์งธ ๊ฒฐ๊ณผ๋ฅผ ์ด์ด๋ถ์ธ ๊ฒ๊ณผ ๊ฐ๋ค. n-1๋ฒ์งธ ๊ฒฐ๊ณผ ์ฌ์ด์ n-1๋ฒ์งธ ๊ฒฐ๊ณผ์ ๊ธธ์ด๋งํผ ๊ณต๋ฐฑ๋ง ๋ฃ์ด์ฃผ๋ฉด ๋๋ค. ์ฆ, n๋ฒ์งธ ๊ฒฐ๊ณผ = n-1๋ฒ์งธ ๊ฒฐ๊ณผ + n-1๋ฒ์งธ ๊ฒฐ๊ณผ ๊ธธ์ด๋งํผ์ ๊ณต๋ฐฑ + n-1๋ฒ์งธ ๊ฒฐ๊ณผ
์ฌ๊ท์ ๊ดํ ํฌ์คํ : https://doleebest.tistory.com/78
'CS > Algorithm' ์นดํ ๊ณ ๋ฆฌ์ ๋ค๋ฅธ ๊ธ
๊ธฐ์ด ์๋ฃ๊ตฌ์กฐ (0) | 2024.08.14 |
---|---|
[๋ฐฑ์ค/python] 1182๋ฒ : ๋ถ๋ถ ์์ด์ ํฉ (0) | 2024.08.11 |
์ฌ๊ท recursive function (0) | 2024.08.09 |
[๋ฐฑ์ค/python] 1018 ์ฒด์คํ ๋ค์ ์น ํ๊ธฐ (0) | 2024.08.04 |
Big O ๋ณต์ต (0) | 2024.04.08 |