-
[Python] ๋ฐฑ์ค - 1463 1๋ก๋ง๋ค๊ธฐ__Python/__Algorithm 2022. 1. 7. 18:32
๋ฌธ์
https://www.acmicpc.net/problem/1463
๐น ๋ฌธ์
์ ์ X์ ์ฌ์ฉํ ์ ์๋ ์ฐ์ฐ์ ๋ค์๊ณผ ๊ฐ์ด ์ธ ๊ฐ์ง ์ด๋ค.
- X๊ฐ 3์ผ๋ก ๋๋์ด ๋จ์ด์ง๋ฉด, 3์ผ๋ก ๋๋๋ค.
- X๊ฐ 2๋ก ๋๋์ด ๋จ์ด์ง๋ฉด, 2๋ก ๋๋๋ค.
- 1์ ๋บ๋ค.
์ ์ N์ด ์ฃผ์ด์ก์ ๋, ์์ ๊ฐ์ ์ฐ์ฐ ์ธ ๊ฐ๋ฅผ ์ ์ ํ ์ฌ์ฉํด์ 1์ ๋ง๋ค๋ ค๊ณ ํ๋ค. ์ฐ์ฐ์ ์ฌ์ฉํ๋ ํ์์ ์ต์๊ฐ์ ์ถ๋ ฅํ์์ค.
๐น ์ ๋ ฅ
์ฒซ์งธ ์ค์ 1๋ณด๋ค ํฌ๊ฑฐ๋ ๊ฐ๊ณ , 106๋ณด๋ค ์๊ฑฐ๋ ๊ฐ์ ์ ์ N์ด ์ฃผ์ด์ง๋ค.
๐น ์ถ๋ ฅ
์ฒซ์งธ ์ค์ ์ฐ์ฐ์ ํ๋ ํ์์ ์ต์๊ฐ์ ์ถ๋ ฅํ๋ค.
ํ์ด ๋ฐฉ๋ฒ
๐น ๋ค์ด๋๋ฏน ํ๋ก๊ทธ๋๋ฐ(DP)
๐น ํ๋ ธ์ต๋๋ค ํด๊ฒฐ ์ฐธ๊ณ > ์ฐ์์ผ๋ก ๋นผ๊ธฐ๋ฅผ ๋๋ฒํ๋ ๊ฒฝ์ฐ https://www.acmicpc.net/board/view/6842
๊ตฌํ ์ฝ๋
import sys N = int(sys.stdin.readline()) arr = [0] * (N+1) for n in range(2,N+1): if n % 6 == 0: arr[n] = min(arr[n//2],arr[n//3])+1 elif n % 2 == 0: arr[n] = min(arr[n-1],arr[n//2])+1 elif n % 3 == 0: arr[n] = min(arr[n-1],arr[n//3])+1 else: arr[n] = min(arr[n-1]+1,arr[n-2]+2) print(arr[N])
์คํ ๊ฒฐ๊ณผ
๐ก
728x90'__Python > __Algorithm' ์นดํ ๊ณ ๋ฆฌ์ ๋ค๋ฅธ ๊ธ
[Python] ๋ฐฑ์ค - 1439 ๋ค์ง๊ธฐ (0) 2022.01.27 [Python] ๋ฐฑ์ค - 1629 ๊ณฑ์ (0) 2022.01.13 [Python] ๋ฐฑ์ค - 2805 ๋๋ฌด ์๋ฅด๊ธฐ (0) 2022.01.07 [Python] ๋ฐฑ์ค - 11399 ATM (0) 2022.01.07 [Python] ๋ฐฑ์ค - 11279 ์ต๋ ํ (0) 2022.01.07