-
[Algo Rhythm๐บ๐] BOJ 1463 - 1๋ก ๋ง๋ค๊ธฐAlgo Rhythm๐บ๐/BOJ 2021. 7. 22. 00:00
๐ซ๋ฌธ์ ๋ถ์
์ฃผ์ด์ง $n\ (1 \le n \le 10^6)$์ ๋ํ์ฌ ์ฌ์ฉ๊ฐ๋ฅํ ์ฐ์ฐ๋ค์ ๋ค์๊ณผ ๊ฐ๋ค.
- $op_1 : n \equiv 0 \pmod{3}์ด๋ฉด,\ n = n \div 3$
- $op_2 : n \equiv 0 \pmod{2}์ด๋ฉด,\ n = n \div 2$
- $op_3 : n = n - 1$
๊ทธ๋ฆฌ๊ณ $n$์ 1๋ก ๋ง๋ค๊ธฐ ์ํด ์ฌ์ฉํ๋ ์ฐ์ฐ์ ์ต์ ํ์๋ฅผ $f(n)$์ด๋ผ๊ณ ํ์.
$n$์ ๋ํ์ฌ $op_1,\ op_2,\ op_3$์ ๋ชจ๋ ์ฌ์ฉํ ์ ์์ ๋ $n$์ 1๋ก ๋ง๋ค๊ธฐ ์ํด ์ฌ์ฉํ๋ ์ฐ์ฐ์ ์ต์ ํ์๋ฅผ ๊ฐ๊ฐ $f_1,\ f_2,\ f_3$๋ผ๊ณ ํ์.
๊ทธ๋ ๋ค๋ฉด $n \equiv 0 \pmod{3}$์ด๋ฉด $op_1$์ ์ฌ์ฉํ์ฌ $n$์ $n \div 3$์ผ๋ก ์ค์ผ ์ ์๊ธฐ ๋๋ฌธ์ $f_1 = f(n \div 3) + 1$์ด๋ค.
๊ทธ๋ฆฌ๊ณ $n \equiv 0 \pmod{2}$์ด๋ฉด $op_2$๋ฅผ ์ฌ์ฉํ์ฌ $n$์ $n \div 2$๋ก ์ค์ผ ์ ์๊ธฐ ๋๋ฌธ์ $f_2 = f(n \div 2 ) + 1$์ด๋ค.
๋ง์ง๋ง์ผ๋ก ๋ชจ๋ $n$์ $op_3$๋ฅผ ์ฌ์ฉํ์ฌ $n$์ $n - 1$๋ก ์ค์ผ ์ ์๊ธฐ ๋๋ฌธ์ $f_3 = f(n - 1) + 1$์ด๋ค.
๋ฐ๋ผ์, $f(n) = \min(f_1,\ f_2,\ f_3)$์ด๋ค.
๐ฅ๋ฌธ์ ํ์ด
$f(n)$์ ์ ํ์์ผ๋ก ํํํ๋ฉด ๋ค์๊ณผ ๊ฐ๋ค.
$f(n)= \begin{cases} 0 & if\ n = 1\\ \min(f_1,f_2,f_3) & else \end{cases}$
โจ๋ณต์ก๋ ๋ถ์
์ฃผ์ด์ง $n\ (1 \le n \le 10^6)$์ ๋ํ์ฌ ์๊ฐ ๋ณต์ก๋์ ๊ณต๊ฐ ๋ณต์ก๋๋ ๊ฐ๊ฐ ๋ค์๊ณผ ๊ฐ๋ค.
โฐ์๊ฐ ๋ณต์ก๋ : $O(n)$
$f(i)\ (1 \le i \le n)$์ ๋ชจ๋ ๊ณ์ฐํด์ผ ํ๊ธฐ ๋๋ฌธ์ $O(n)$์ด ์์๋จ.
๐ ๊ณต๊ฐ ๋ณต์ก๋ : $O(n)$
$f(i)\ (1 \le i \le n)$์ ์ ์ฅํ ๊ณต๊ฐ์ด ํ์ํ๊ธฐ ๋๋ฌธ์ $O(n)$์ด ์์๋จ.
๐์ฝ๋
๐๋ฌธ์ ์ถ์ฒ
https://www.acmicpc.net/problem/1463
'Algo Rhythm๐บ๐ > BOJ' ์นดํ ๊ณ ๋ฆฌ์ ๋ค๋ฅธ ๊ธ
[Algo Rhythm๐บ๐] BOJ 16926 - ๋ฐฐ์ด ๋๋ฆฌ๊ธฐ 1 (0) 2021.08.14 [Algo Rhythm๐บ๐] BOJ 2225 - ํฉ๋ถํด (0) 2021.07.22 [Algo Rhythm๐บ๐] BOJ 10971 - ์ธํ์ ์ํ 2 (0) 2021.07.10 [Algo Rhythm๐บ๐] BOJ 1759 - ์ํธ ๋ง๋ค๊ธฐ (0) 2021.06.30 [Algo Rhythm๐บ๐] BOJ 18290 - NM๊ณผ K(1) (0) 2021.06.30