Algo Rhythm๐บ๐
-
[Algo Rhythm๐บ๐] BOJ 18290 - NM๊ณผ K(1)Algo Rhythm๐บ๐/BOJ 2021. 6. 30. 17:41
๐ซ๋ฌธ์ ๋ถ์ ํฌ๊ธฐ๊ฐ $n \times m\ (1 \le n,\ m \le 10)$์ธ ๊ฒฉ์ํ์ $g$๋ผ๊ณ ํ์. $g$์ ๊ฐ ์นธ์๋ ์ ์๊ฐ ํ๋์ฉ ๋ค์ด์๋๋ฐ ์ธ์ ํ ์นธ๋ค์ ์ ์ธํ๊ณ $k\ (1 \le k \le \min (4, n \times m))$๊ฐ์ ์นธ์ ์ ํํ์ฌ ๊ฐ ์นธ์ ๋ค์ด์๋ ๋ชจ๋ ์๋ค์ ๋ํ ๋ ๋์ฌ ์ ์๋ ๊ฐ๋ค ์ค ์ต๋๊ฐ์ ๊ตฌํด์ผ ํ๋ค. $g$์ ๊ฐ ์นธ์ ํ๋์ vertex๋ผ๊ณ ์๊ฐํด๋ณด์. ๊ทธ๋ ๋ค๋ฉด ์ด ๋ฌธ์ ๋ $n \times m$๊ฐ์ vertex๋ค ์ค์์ ์ธ์ ํ ์นธ๋ค์ ์ ์ธํ๊ณ $k$๊ฐ์ vertex๋ฅผ ์ ํํ ๋ ์ป์ ์ ์๋ ์ต๋๊ฐ์ ๊ตฌํ๋ backtracking ๋ฌธ์ ๋ก ์ดํดํ ์ ์๋ค. ๐ฅ๋ฌธ์ ํ์ด $n \times m$๊ฐ์ ์นธ ์ค $k$๊ฐ์ ์นธ์ ์ ํํ ๋ ํ ๊ฐ์ง ์กฐ๊ฑด์ ์ด๋ฏธ ์ ํ..
-
[Algo Rhythm๐บ๐] BOJ 9095 - 1, 2, 3 ๋ํ๊ธฐAlgo Rhythm๐บ๐/BOJ 2021. 6. 29. 00:06
๐ซ๋ฌธ์ ๋ถ์ ํ ์คํธ ์ผ์ด์ค์ ๊ฐ์๋ฅผ $t$, ๊ฐ ํ ์คํธ ์ผ์ด์ค๋ง๋ค ์ฃผ์ด์ง๋ ์ ์๋ฅผ $n (1 \le n \lt 11)$์ด๋ผ๊ณ ํ์. ๊ทธ๋ฆฌ๊ณ $n$์ $1,\ 2, \ 3$์ ํฉ์ผ๋ก ๋ํ๋ด๋ ๋ฐฉ๋ฒ์ ์๋ฅผ $f(n)$์ด๋ผ๊ณ ํ์. ๊ฐ ํ ์คํธ์ผ์ด์ค๋ง๋ค $f(n)$์ ์ถ๋ ฅํด์ผ ํ๋ฉฐ, ํฉ์ ๋ํ๋ผ ๋๋ ์๋ฅผ 1๊ฐ ์ด์ ์ฌ์ฉํด์ผ ํ๋ค. $f(n)$์ 1๋ถํฐ ์ฐจ๋ก๋๋ก ์๋์ ๊ฐ๋ค. ์ด๋ ํ๋์ ๋๊ทธ๋ผ๋ฏธ๋ก ํ์๋ ์๋ค์ ๊ด์ฐฐํ๋ฉด ๋ถ๋ช ํ ์ฐ์์ ์ธ ๊ด๊ณ๊ฐ ์๋ค๋ ๊ฒ์ ์ ์ ์๋ค. ๋ฐ๋ผ์ ์ด ๋ฌธ์ ๋ ๊ทธ '์ฐ์์ ์ธ ๊ด๊ณ'๋ฅผ ์ด์ฉํ์ฌ ํด๊ฒฐํ ์ ์๋ค. ๐ฅ๋ฌธ์ ํ์ด ์์ ์ธ๊ธํ ์ฐ์์ ์ธ ๊ด๊ณ๋ ๋ค์๊ณผ ๊ฐ๋ค. $\begin{matrix} f(i) &=& \sum_{j = 1}^3 g(i, j) & (1\le i\lt 11, i ..
-
[Algo Rhythm๐บ๐] BOJ 1748 - ์ ์ด์ด์ฐ๊ธฐ 1Algo Rhythm๐บ๐/BOJ 2021. 6. 28. 19:17
๋ฌธ์ ๋ถ์ 1๏ธโฃ. ๋์ ํ์ด ์์ฐ์ $i (1 \le i \le 8)$, $num \in [10^{i - 1}, 10^i)$๋ฅผ ๋ง์กฑํ๋ ์์ฐ์ $num$, $num$์ ๋ฐ๋ผ ๋ํด์ง๋ ๊ธ์ ์, ๊ทธ๋ฆฌ๊ณ $num$์ ๊ฐ์๋ฅผ ์ ๋ฆฌํ ํ๋ ์๋์ ๊ฐ๋ค. ์ ๋ ฅ์ผ๋ก ์ฃผ์ด์ง $n (1 \le n \le 10^8)$์ ์๋ฆฟ์๋ฅผ $\alpha$๋ผ๊ณ ํ๊ณ 1๋ถํฐ $n$๊น์ง ์ด์ด ์ธ ๋ ๋ง๋ค์ด์ง๋ ์๋ก์ด ์์ ์๋ฆฟ์๋ฅผ $f(n)$์ด๋ผ๊ณ ํ ๋, $f(n)$์ ๊ตฌํ๋ ๊ฒ์ด ์ด ๋ฌธ์ ์ ํต์ฌ์ด๋ค. 2๏ธโฃ. ๋ค๋ฅธ ๋ถ์ ํ์ด (๊น๋โจ) ์ ๋ ฅ์ผ๋ก ์ฃผ์ด์ง $n (1 \le n \le 10^8)$ ์ดํ์ธ ๋ชจ๋ ์์ฐ์๋ค์ ๋ํ์ฌ ๊ฐ ์๋ฆฌ์ ๋ณ๋ก ๋๋ ์ ์๊ฐํด๋ณด์. 1์ ์๋ฆฌ๊ฐ ์๋ ์๋ 1๋ถํฐ $n$๊น์ง ์ด $(n - 1 + 1)$๊ฐ์ด๋ค..
-
[Algo Rhythm๐บ๐] BOJ 17425 - ์ฝ์์ ํฉAlgo Rhythm๐บ๐/BOJ 2021. 6. 24. 21:43
๋ฌธ์ ๋ถ์ ์ฝ์์ ์ฑ์ง ์ค ํ๋๋ ๋ ์์ฐ์ $a, b$์ ๋ํ์ฌ $a$๊ฐ $b$์ ๋ฐฐ์์ด๋ฉด $b$๋ $a$์ ์ฝ์(๋ค) ์ค ํ๋๋ผ๋ ๊ฒ์ด๋ค. ๊ทธ๋ฆฌ๊ณ ์ด ๋ฌธ์ ๋ ์์ฐ์ $n(1 \le n \le 10^6)$์ ์ ๋ ฅํ ๋ $g(n)$์ ์ถ๋ ฅํ ๊ฒ์ ์๊ตฌํ๋ค. ์ด๋ $g(n)$์ ์๋์ ๊ฐ์ ์์์ผ๋ก ์ ์ํ ์ ์๋ค. $g(n)= \begin{cases} g(n - 1) + f(n) & n \gt 1\\ 1 & n = 1 \end{cases}$ ์์ ๋งํ ๋ ๊ฐ์ง๋ฅผ ์ข ํฉํ ๋ ์ด ๋ฌธ์ ๋ ์ฝ์์ ์ฑ์ง์ ์ด์ฉํ์ฌ ๋ชจ๋ $n$์ ๋ํ์ฌ $g(n)$์ ๊ตฌํ์ฌ ์ ์ฅํ ๋ค์ ํ ์คํธ์ผ์ด์ค๋ก $n$์ ์ํ๋ ์์ฐ์ $a$๊ฐ ๋ค์ด์ฌ ๋๋ง๋ค $g(a)$๋ฅผ ์ถ๋ ฅํ๋ ๋ฌธ์ ๋ก ์ดํดํ ์ ์๋ค. ๋ฌธ์ ํ์ด 1. $g(n)$์ ์ ์ฅํ..
-
[Algo Rhythm๐บ๐] BOJ 17427 - ์ฝ์์ ํฉ 2Algo Rhythm๐บ๐/BOJ 2021. 6. 24. 01:42
๋ฌธ์ ๋ถ์ ์ ๋ ฅ์ผ๋ก ์ฃผ์ด์ง๋ ์์ฐ์๋ฅผ $n (1 \le n \le 10^6)$ ๊ทธ๋ฆฌ๊ณ $n$๋ณด๋ค ์๊ฑฐ๋ ๊ฐ์ ์์ฐ์๋ฅผ $i$๋ผ๊ณ ํ์. ์์ฐ์ $a$๊ฐ ์์ฐ์ $b$๋ก ๋๋์ด ๋จ์ด์ง๋ค๋ฉด ์ฆ, $a$๊ฐ $b$์ ๋ฐฐ์๋ผ๋ฉด $b$๋ $a$์ ์ฝ์์ด๋ค. ๋ฐ๋ผ์, ์ด ๋ฌธ์ ๋ $i$์ ์ํ๋ ํ ์์ฐ์์ ๋ฐฐ์์ ๊ฐ์์ ๊ทธ ์์ฐ์๋ฅผ ๊ณฑํ ๊ฐ๋ค์ ๋ํ์ฌ $g(n) = \sum_{i=1}^n f(i)$์ ๊ตฌํ๋ ๋ฌธ์ ๋ก ์ดํดํ ์ ์๋ค. ๋ฌธ์ ํ์ด $i$๋ฅผ 1๋ถํฐ $n$๊น์ง ๋ฐ๋ณตํ์ฌ $i$์ ๋ฐฐ์์ ๊ฐ์์ $i$๋ฅผ ๊ณฑํ ๊ฐ๋ค์ ๋ํ๋ค. ์ด๋ $i$์ ๋ฐฐ์๋ $n/i$๊ฐ์ด๋ค. ๊ทธ๋ฆฌ๊ณ $i > n/2$์ผ ๋ $n$๋ณด๋ค ์์ ์์ฐ์๋ค ์ค $i$์ ๋ฐฐ์๋ $i$ ์๊ธฐ ์์ ๋ฟ์ด๋ค. ๋ฐ๋ผ์ ๊ทธ ๊ฒฝ์ฐ์๋ $i$๋ง ๋ํ๋ค. ๋ณต์ก๋ ๋ถ์..
-
[Algo Rhythm๐บ๐] BOJ 4375 - 1Algo Rhythm๐บ๐/BOJ 2021. 6. 23. 21:55
๋ฌธ์ ๋ถ์ 1๋ก๋ง ์ด๋ฃจ์ด์ง ํ ์ ์๋ฅผ $x$, 2์ 5๋ก ๋๋์ด ๋จ์ด์ง์ง ์๋ ์ ์๋ฅผ $n (1 \le n \le 10^5)$์ด๋ผ๊ณ ํ์. ์ด ์ ์์ ์ค๋ฅธ์ชฝ ๋์ 1์ ๋ถ์ด๊ธฐ ์ํด์๋ ์ ์์ ์๋ฆฟ์๋ฅผ ํ ์๋ฆฌ ์ฌ๋ฆฐ ํ 1์ ๋ํ๋ฉด ๋๋ค. ์ฆ, $10 \times x + 1$์ ํ๋ฉด ๋๋ค. ํ์ง๋ง overflow๊ฐ ๋ฐ์ํ ์ ์๊ธฐ ๋๋ฌธ์ ๊ณ์ํด์ ์ค๋ฅธ์ชฝ ๋์ 1์ ๋ถ์ผ ์ ์๋ค. ๋คํํ๋ ๋ฌธ์ ์์ ์๊ตฌํ๋ ๊ฒ์ $x$ ์์ฒด๊ฐ ์๋๋ผ $x \mod n == 0$์ ๋ง์กฑํ ๋์ ์๋ฆฟ์์ด๋ค. ๋ฐ๋ผ์, ์ค์ํ ๊ฒ์ $x$๊ฐ ์๋๋ผ $x \mod n$์ด๋ผ๋ ๊ฒ์ ์ ์ ์๋ค. ๊ทธ๋์ ์ ์์ ์ค๋ฅธ์ชฝ ๋์ 1์ ๋ถ์ผ ๋ $x = 10 \times x + 1$์ด ์๋ $x = (10 \times x + 1) \mod n..
-
[Algo Rhythm๐บ๐]BOJ 6588 - ๊ณจ๋๋ฐํ์ ์ถ์ธกAlgo Rhythm๐บ๐/BOJ 2021. 6. 23. 17:45
๋ฌธ์ ๋ถ์ ์ด ๋ฌธ์ ๋ 4๋ณด๋ค ํฐ ์ด๋ค ์ง์ $x (6 \le x \le 10^6)$๊ฐ ๋ ํ์์ธ ์์ $a, b (a \le b)$์ ํฉ์ผ๋ก ๋ํ๋ผ ์ ์๋์ง ํ๋ณํ๋ ๋ฌธ์ ์ด๋ค. ์ด๋ ์ฃผ์ํ ์ ์ ๊ณจ๋๋ฐํ์ ์ถ์ธก์ $10^{18}$ ์ดํ์์ ์ฐธ์์ด ํ์ธ๋์๊ธฐ ๋๋ฌธ์ ๋ ํ์ ์์์ ํฉ์ผ๋ก ๋ํ๋ด์ง ๋ชป ํ๋ ๊ฒฝ์ฐ๋ ์๊ฐํ์ง ์์๋ ๋๋ค๋ ๊ฒ์ด๋ค. ๋ฌธ์ ํ์ด 1. '์์ ํ๋ณ ์๊ณ ๋ฆฌ์ฆ' ์์ฉ ์ฃผ์ด์ง $x$์ ๋ํ์ฌ $a$์ ๊ฐ๋ฅํ ์ต์๊ฐ์ธ 3๋ถํฐ $x - a$์ธ $b$๊ฐ 2๋ณด๋ค ํฌ์ง ์์ ๋๊น์ง $a, b$ ๋ชจ๋ ์์์ธ์ง ํ๋ณํ๋ค. ๋ง์ฝ ๋ชจ๋ ์์๋ผ๋ฉด $x = a + b$๋ฅผ ์ถ๋ ฅํ ๋ค ๋ฐ๋ณต๋ฌธ์ ํ์ถํ๊ณ ๊ทธ๋ ์ง ์๋ค๋ฉด $a$๋ฅผ 2์ฉ ์ฆ๊ฐํ๊ณ ์ ๊ณผ์ ์ ๋ฐ๋ณตํ๋ค. ์ด๋ 2์ฉ ์ฆ๊ฐํ๋ ์ด์ ๋ ์ง์๋ ์ ๋ ์์๊ฐ ..
-
[Algo Rhythm๐บ๐]BOJ 2309 - ์ผ๊ณฑ ๋์์ดAlgo Rhythm๐บ๐/BOJ 2021. 6. 22. 20:02
๋ฌธ์ ๋ถ์ ๋ฌธ์ ์์ ์ฃผ์ด์ง๋ ์ํ ๋์์ด๋ค์ ํค์ ํฉ์ ์ผ๊ณฑ ๋์์ด๋ค์ ํค์ ํฉ์ธ 100๋ณด๋ค ํฌ๋ค. ๋ฐ๋ผ์ ์ด ๋ฌธ์ ๋ $i$๋ฒ์งธ ๋์์ด์ $j$๋ฒ์งธ ๋์์ด $(1 \le i, j \le n)$์ ํฉ์ด ์ด๊ณผ๊ฐ๊ณผ ์ผ์นํ๋ $(i, j)$์์ ์ฐพ๋ ๋ฌธ์ ๋ก ์ดํดํ ์ ์๋ค. ๋ฌธ์ ํ์ด ์ํ ๋์์ด์ ํค๋ฅผ ๋ฐฐ์ด์ ์ ์ฅํ ๋ค, ์ด๋ฅผ ์ค๋ฆ์ฐจ์์ผ๋ก ์ ๋ ฌํ๋ค. ์๋ํ๋ฉด ์ผ๊ณฑ ๋์์ด์ ํค๋ฅผ ์ถ๋ ฅํ ๋ ์ค๋ฆ์ฐจ์์ผ๋ก ์ถ๋ ฅํด์ผ ํ๊ธฐ ๋๋ฌธ์ด๋ค. ๋ค์์ผ๋ก ์ด์ค ๋ฐ๋ณต๋ฌธ์ ํตํด $(i, j)$์์ ์ฐพ๋๋ค. ๋ง์ฝ ์ฐพ์๋ค๋ฉด $i$๋ฒ์งธ ๋์์ด์ $j$๋ฒ์งธ ๋์์ด๋ฅผ ์ ์ธํ ๋ชจ๋ ๋์์ด๋ค์ ํค๋ฅผ ์ฐจ๋ก๋๋ก ์ถ๋ ฅํ ๋ค ํ๋ก๊ทธ๋จ์ ์ข ๋ฃํ๋ค. ๋ณต์ก๋ ๋ถ์ ๋์์ด $n$๋ช ์ ํค๊ฐ ์ ๋ ฅ์ผ๋ก ์ฃผ์ด์ง ๋, ์๊ฐ ๋ณต์ก๋์ ๊ณต๊ฐ ๋ณต์ก๋๋ ๋ค์๊ณผ ๊ฐ๋ค. ์๊ฐ ๋ณต..