๋ฐฑ์ค 1463 ํ์ด์ฌ
https://www.acmicpc.net/problem/1463
1463๋ฒ: 1๋ก ๋ง๋ค๊ธฐ
์ฒซ์งธ ์ค์ 1๋ณด๋ค ํฌ๊ฑฐ๋ ๊ฐ๊ณ , 106๋ณด๋ค ์๊ฑฐ๋ ๊ฐ์ ์ ์ N์ด ์ฃผ์ด์ง๋ค.
www.acmicpc.net
์ ์ X๊ฐ ์ฃผ์ด์ก์ ๋
- 3์ผ๋ก ๋๋์ด ๋จ์ด์ง๋ฉด 3์ผ๋ก ๋๋๊ณ
- 2๋ก ๋๋์ด ๋จ์ด์ง๋ฉด 2๋ก ๋๋๊ณ
- ๊ทธ ์ด์ธ๋ 1์ ๋บ๋ค.
ํด๋น ๊ท์น์ ๋ง์ถฐ์ ์ฐ์ฐ ํ์์ ์ต์๊ฐ์ ๊ตฌํ๋ ๋ฌธ์ ์ด๋ค.
๋ฌธ์ ๋ฅผ ๋ณด๊ณ ๋ฑ ์๊ฐ์ด ๋ ์๊ณ ๋ฆฌ์ฆ์ด ๋์ ๊ณํ๋ฒ์ด์์ต๋๋ค.
- ์ด๊ธฐ๊ฐ์ผ๋ก ์ค์ ํ ๊ฐ์ด ๋ช ํํ๊ณ
- ๊ธฐ์กด์ ์ฐ์ฐ๋ ๊ฐ์ ์ฌ์ฌ์ฉํ๋ ๋ฉ๋ชจ์ด์ ์ด์ ์ด ๋ฑ ๋ง์ ๋จ์ด์ก๋ค.
Python ํ์ด 1
import sys
read = sys.stdin.readline
N = int(read())
cache = [-1] * (N+3)
cache[1] = 0
cache[2] = cache[3] = 1
for i in range(4, N+1):
cnt = 10**6
if i % 3 == 0:
cnt = min(cache[i//3], cnt)
if i % 2 == 0:
cnt = min(cache[i//2], cnt)
cache[i] = min(cache[i-1], cnt) + 1
print(cache[N])
- cache๋ ๋ฉ๋ชจ์ด์ ์ด์
์ ์ํ ์ฌ์ฌ์ฉ ๊ฐ์ ์ ์ฅํ๊ธฐ ์ํ ์ฉ๋๋ก ์ฌ์ฉํ๋ค.
- cache์ ํฌ๊ธฐ๋ N๋ณด๋ค 3์ ํฌ๊ฒ ์ก์๋ค. 1, 2๊ฐ N์ผ๋ก ๋ค์ด์ฌ ๊ฒฝ์ฐ ์ด๊ธฐ ๊ฐ ์ค์ ํ ๋ Index Out if Bounds ์ค๋ฅ๋ฅผ ํผํ๊ธฐ ์ํด์์ด๋ค.
- 1,2,3 ์ผ ๋ ์ด๊ธฐ ๊ฐ์ด ๋ช ํํด์ ์ค์ ์ ๋จผ์ ์งํํด์คฌ๋ค.
- ์ดํ 4๋ถํฐ N๊น์ง ์บ์๊ฐ์ ์ฌ์ฌ์ฉํ๋ฉด์ ์ฐ์ฐ์ ์งํํ๋ค.
์ ํ์ ์ธ ๋์ ๊ณํ๋ฒ ๋ฌธ์ ์ด๋ค.
๊ทธ๋ฌ๋ ํด๋น ํ์ด๋ก ์๊ฐ๋ณด๋ค ์ฐ์ฐ ์๊ฐ์ด ์ค๋๊ฒฐ๋ฌ์ ๋ค๋ฅธ ๋ฐฉ๋ฒ์ ์ฐพ์๋ดค๋ค.
Python ํ์ด 2
ํ์ด1๋ณด๋ค 10๋ฐฐ์ด์ ๋น ๋ฅด๋ค. ์ฐ์ ๋ฆฌ์คํธํํ๋ก N๊น์ง ๋ชจ๋ ์๋ฅผ ํ์ธํ์ง ์๊ณ ์๋ฅผ ๋๋๋ฉด์ ๊ผญ ํ์ํ ๊ฐ๋ง ํ์ธํ๋ค๋ ์ ์์ ํจ์ฌ ๋น ๋ฅด๋ค. ๊ทธ๋ฌ๋... ์์ ํ์ด๋ณด๋ค ์ดํดํ๋๋ฐ ์๊ฐ์ด ์์๋๋ค. ๊ฐ์ธ์ ์ผ๋ก ์ฌ๊ทํจ์๋ฅผ ๋ง์ด ์ด๋ ค์ํด์ ์ด๋ฐ ํ์ด๋ฅผ ๋ณด๋ฉด ์ฐธ ์ ๊ธฐํ ๋ฐ๋ฆ์ด๋ค.
import sys
read = sys.stdin.readline
N = int(read())
cache = {1: 0, 2: 1}
def dp(n):
if n in cache:
return cache[n]
# ํต์ฌ ์ฝ๋
cnt = 1 + min(dp(n//3) + n%3, dp(n//2) + n%2)
cache[n] = cnt
return cnt
print(dp(N))
- ๋ฆฌ์คํธ ๋์ ๋์ ๋๋ฆฌ๋ฅผ ์ฌ์ฉํด์ ๊ฐ์ ์ฐพ๋ ์ฐ์ฐ ์๋๋ฅผ ์ค์ผ ์ ์๋ค.
- ์ฌ๊ทํจ์๋ฅผ ์ฌ์ฉํ๋ค.
- ์บ์์ ๊ฐ์ด ์๋๊ฒฝ์ฐ ๊ฐ์ ๋ฐํํ๊ณ
- ํต์ฌ์ฝ๋๋ฅผ ๋ณด๋ฉด... ์ฌ๊ทํจ์์ ๊ฐ๊ฐ 3๊ณผ 2๋ก ๋๋ ๋ชซ์ ๋๋จธ์ง๋ฅผ ๋ํด์ ์ต์๊ฐ์ ๊ตฌํ๋ค.
ํต์ฌ์ฝ๋ ํ์ด
์ฝ๋๋ง ๋ณด๋ฉด... ๋๋จธ์ง๊ฐ์ ์ ๋ํ๋์ง ์ดํด ์๋ ์ ์๋ค. ์ ๋ ์ดํดํ๋๋ฐ ์๊ฐ์ด ์ค๋ ๊ฑธ๋ ธ๋๋ฐ์... ๋๋จธ์ง๊ฐ์ ๋ํ๋ ์ด์ ๋ 7 ์ด๋ 11 ์ฒ๋ผ 2์ 3์ผ๋ก ๋๋ ์ ์๋ ๊ฒฝ์ฐ ๋ฌด์กฐ๊ฑด 1์ 1๋ฒ ์ด์ ๋นผ๊ณ ์งํ์ ํ๊ฒ๋ฉ๋๋ค.
- 2๋ก ๋๋๋ ค๊ณ ํ๋ฉด ๋๋จธ์ง๊ฐ 1
- 3์ผ๋ก ๋๋๋ ค๊ณ ํ๋ฉด ๋๋จธ์ง๊ฐ 1, 2
2์ 3์ ๋ฐฐ์๊ฐ ์๋ ์ซ์์ ๊ท์น์ ์์ ๊ฐ์ต๋๋ค. ๊ทธ๋์ ์ด๋ฐ ๊ฒฝ์ฐ 2๊ฐ์ง ๋ถ๊ธฐ๋ฅผ ํ๊ฒ ๋ฉ๋๋ค.
โป ์์ N=7 ์ธ ๊ฒฝ์ฐ 3๊ณผ 2๋ก ๋๋ด์ ๋ ๋๋จธ์ง๊ฐ ๋ชจ๋ 1
ํด๋น ๊ฒฝ์ฐ 3์ด๋ 7์ด๋ -1์ ํ๋ฒ์ฉ ์ฐ์ฐํ๊ณ ์งํํด์ผ ํ๊ธฐ ๋๋ฌธ์ ๋๋จธ์ง 1์ ๋ํด์ฃผ๋ ๊ฒ์ ์ฝ๊ฒ ์ดํด๊ฐ ๋๋ค.
โป ์์ N=11 ์ธ ๊ฒฝ์ฐ 3๊ณผ 2๋ก ๋๋ด์ ๋ ๋๋จธ์ง๊ฐ ๊ฐ๊ฐ 2์ 1
ํด๋น ๊ฒฝ์ฐ๋ ๋๊ฐ์ง ๋ฃจํธ๋ก ๋๋ ์ ์งํํ๊ฒ ๋ค๊ณ ์๊ฐํ์๋ฉด ๋ ๊ฒ ๊ฐ์ต๋๋ค.
- -1์ ๋๋ฒ ํด์ 3์ผ๋ก ๋๋๋ ค๋ ๋ฃจํธ
- -1์ ํ๋ฒ ํด์ 2๋ก ๋๋๋ ค๋ ๋ฃจํธ
๊ทธ๋ฆผ์ผ๋ก ์์๋ฅผ ๋ณด๋ฉด ์๋์ ๊ฐ์ต๋๋ค.
11์์ 9๋ก ๊ฐ์ 3์ ๋๋๋ ๋ฃจํธ๋ก... 2๋ฒ์ -1 ์ฐ์ฐ์ ํด์ผํ๊ธฐ ๋๋ฌธ์ ๋๋จธ์ง์ธ 2๋ฅผ ๋ํ๊ณ
11์์ 10์ผ๋ก ๊ฐ์ 2๋ก ๋๋๋ ๋ฃจํธ๋ก... 1๋ฒ์ -1 ์ฐ์ฐ์ ํด์ผํ๊ธฐ ๋๋ฌธ์ ๋๋จธ์ง์ธ 1์ ๋ํ๋ ์๋ฆฌ์ ๋๋ค.
๋๊ธ