BOJ-2447
[C++] ๋ณ ์ฐ๊ธฐ - 10
๋ฌธ์ ์ฌ๊ท์ ์ธ ํจํด์ผ๋ก ๋ณ์ ์ฐ์ด ๋ณด์. N์ด 3์ ๊ฑฐ๋ญ์ ๊ณฑ(3, 9, 27, ...)์ด๋ผ๊ณ ํ ๋, ํฌ๊ธฐ N์ ํจํด์ NรN ์ ์ฌ๊ฐํ ๋ชจ์์ด๋ค. ํฌ๊ธฐ 3์ ํจํด์ ๊ฐ์ด๋ฐ์ ๊ณต๋ฐฑ์ด ์๊ณ , ๊ฐ์ด๋ฐ๋ฅผ ์ ์ธํ ๋ชจ๋ ์นธ์ ๋ณ์ด ํ๋์ฉ ์๋ ํจํด์ด๋ค. *** * * *** N์ด 3๋ณด๋ค ํด ๊ฒฝ์ฐ, ํฌ๊ธฐ N์ ํจํด์ ๊ณต๋ฐฑ์ผ๋ก ์ฑ์์ง ๊ฐ์ด๋ฐ์ (N/3)ร(N/3) ์ ์ฌ๊ฐํ์ ํฌ๊ธฐ N/3์ ํจํด์ผ๋ก ๋๋ฌ์ผ ํํ์ด๋ค. ์๋ฅผ ๋ค์ด ํฌ๊ธฐ 27์ ํจํด์ ์์ ์ถ๋ ฅ 1๊ณผ ๊ฐ๋ค. ์
๋ ฅ ์ฒซ์งธ ์ค์ N์ด ์ฃผ์ด์ง๋ค. N์ 3์ ๊ฑฐ๋ญ์ ๊ณฑ์ด๋ค. ์ฆ ์ด๋ค ์ ์ k์ ๋ํด N=3k์ด๋ฉฐ, ์ด๋ 1โคk<8์ด๋ค. ์ถ๋ ฅ ์ฒซ์งธ ์ค๋ถํฐ N๋ฒ์งธ ์ค๊น์ง ๋ณ์ ์ถ๋ ฅํ๋ค. ์์ ์
๋ ฅ 1 27 ์์ ์ถ๋ ฅ 1 ***************..
0
2022.11.03