๋ชฉ๋ก์ ์ฒด ๊ธ (1005)
๐ ๊ณต๋ถํ๋ ์ง์ง์ํ์นด๋ ์ฒ์์ด์ง?
์ฐ๋ฆฌ๋๋ผ ๊ณ ์ ์ ์ท๋์ด๋ ๋ค ๊ฐ์ ์ท์ง์ ๋์ ธ์ ๋ฐฐ(0)์ ๋ฑ(1)์ด ๋์ค๋ ์ซ์๋ฅผ ์ธ์ด ๋, ๊ฐ, ๊ฑธ, ์ท, ๋ชจ๋ฅผ ๊ฒฐ์ ํ๋ค ๋ค ๊ฐ ์ท์ง์ ๋์ ธ์ ๋์จ ๊ฐ ์ท์ง์ ๋ฐฐ ํน์ ๋ฑ ์ ๋ณด๊ฐ ์ฃผ์ด์ง ๋ ๋(๋ฐฐ ํ ๊ฐ, ๋ฑ ์ธ ๊ฐ), ๊ฐ(๋ฐฐ ๋ ๊ฐ, ๋ฑ ๋ ๊ฐ), ๊ฑธ(๋ฐฐ ์ธ ๊ฐ, ๋ฑ ํ ๊ฐ), ์ท(๋ฐฐ ๋ค ๊ฐ), ๋ชจ(๋ฑ ๋ค ๊ฐ) ์ค ์ด๋ค ๊ฒ์ธ์ง๋ฅผ ๊ฒฐ์ ํ๋ ํ๋ก๊ทธ๋จ์ ์์ฑ ์ ๋ ฅ ์ฒซ์งธ ์ค๋ถํฐ ์ ์งธ ์ค๊น์ง ๊ฐ ์ค์ ๊ฐ๊ฐ ํ ๋ฒ ๋์ง ์ท์ง๋ค์ ์ํ๋ฅผ ๋ํ๋ด๋ ๋ค ๊ฐ์ ์ ์(0 ๋๋ 1)๊ฐ ๋น์นธ์ ์ฌ์ด์ ๋๊ณ ์ฃผ์ด์ง๋ค. ์ถ๋ ฅ ์ฒซ์งธ ์ค๋ถํฐ ์ ์งธ ์ค๊น์ง ํ ์ค์ ํ๋์ฉ ๊ฒฐ๊ณผ๋ฅผ ๋๋ A, ๊ฐ๋ B, ๊ฑธ์ C, ์ท์ D, ๋ชจ๋ E๋ก ์ถ๋ ฅํ๋ค // [2490] ์ท๋์ด /* ์ฐ๋ฆฌ๋๋ผ ๊ณ ์ ์ ์ท๋์ด๋ ๋ค ๊ฐ์ ์ท์ง์ ๋์ ธ์ ๋ฐฐ(0)์ ๋ฑ..
7๊ฐ์ ์์ฐ์๊ฐ ์ฃผ์ด์ง ๋, ์ด๋ค ์ค ํ์์ธ ์์ฐ์๋ค์ ๋ชจ๋ ๊ณจ๋ผ ๊ทธ ํฉ์ ๊ตฌํ๊ณ , ๊ณ ๋ฅธ ํ์๋ค ์ค ์ต์๊ฐ์ ์ฐพ๋ ํ๋ก๊ทธ๋จ์ ์์ฑํ์์ค. ์๋ฅผ ๋ค์ด, 7๊ฐ์ ์์ฐ์ 12, 77, 38, 41, 53, 92, 85๊ฐ ์ฃผ์ด์ง๋ฉด ์ด๋ค ์ค ํ์๋ 77, 41, 53, 85์ด๋ฏ๋ก ๊ทธ ํฉ์ 77 + 41 + 53 + 85 = 256 ์ด ๋๊ณ , 41 x) { min = x; } } } // ์์๊ฐ ์๋ค๋ฉด if (sum == 0) { cout
ํผ๋ณด๋์น ์๋ 0๊ณผ 1๋ก ์์ํ๋ค. 0๋ฒ์งธ ํผ๋ณด๋์น ์๋ 0์ด๊ณ , 1๋ฒ์งธ ํผ๋ณด๋์น ์๋ 1์ด๋ค. ๊ทธ ๋ค์ 2๋ฒ์งธ ๋ถํฐ๋ ๋ฐ๋ก ์ ๋ ํผ๋ณด๋์น ์์ ํฉ์ด ๋๋ค. ์ด๋ฅผ ์์ผ๋ก ์จ๋ณด๋ฉด Fn = Fn-1 + Fn-2 (n ≥ 2)๊ฐ ๋๋ค. n=17์ผ๋ ๊น์ง ํผ๋ณด๋์น ์๋ฅผ ์จ๋ณด๋ฉด ๋ค์๊ณผ ๊ฐ๋ค. 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597 n์ด ์ฃผ์ด์ก์ ๋, n๋ฒ์งธ ํผ๋ณด๋์น ์๋ฅผ ๊ตฌํ๋ ํ๋ก๊ทธ๋จ์ ์์ฑ ์ ๋ ฅ ์ฒซ์งธ ์ค์ n์ด ์ฃผ์ด์ง๋ค. n์ 45๋ณด๋ค ์๊ฑฐ๋ ๊ฐ์ ์์ฐ์ ์ถ๋ ฅ ์ฒซ์งธ ์ค์ n๋ฒ์งธ ํผ๋ณด๋์น ์๋ฅผ ์ถ๋ ฅํ๋ค // [2747] ํผ๋ณด๋์น ์ /* ํผ๋ณด๋์น ์๋ 0๊ณผ 1๋ก ์์ํ๋ค. 0๋ฒ์งธ ํผ๋ณด๋์น ์๋ 0์ด๊ณ , 1๋ฒ์งธ ํผ๋ณด๋์น ์๋..
์ปดํจํฐ๋ฅผ ์ ์กฐํ๋ ํ์ฌ์ธ KOI ์ ์์์๋ ์ ์กฐํ๋ ์ปดํจํฐ๋ง๋ค 6์๋ฆฌ์ ๊ณ ์ ๋ฒํธ๋ฅผ ๋งค๊ธด๋ค. ๊ณ ์ ๋ฒํธ์ ์ฒ์ 5์๋ฆฌ์๋ 00000๋ถํฐ 99999๊น์ง์ ์ ์ค ํ๋๊ฐ ์ฃผ์ด์ง๋ฉฐ 6๋ฒ์งธ ์๋ฆฌ์๋ ๊ฒ์ฆ์๊ฐ ๋ค์ด๊ฐ๋ค. ๊ฒ์ฆ์๋ ๊ณ ์ ๋ฒํธ์ ์ฒ์ 5์๋ฆฌ์ ๋ค์ด๊ฐ๋ 5๊ฐ์ ์ซ์๋ฅผ ๊ฐ๊ฐ ์ ๊ณฑํ ์์ ํฉ์ 10์ผ๋ก ๋๋ ๋๋จธ์ง์ด๋ค. ์๋ฅผ ๋ค์ด ๊ณ ์ ๋ฒํธ์ ์ฒ์ 5์๋ฆฌ์ ์ซ์๋ค์ด 04256์ด๋ฉด, ๊ฐ ์ซ์๋ฅผ ์ ๊ณฑํ ์๋ค์ ํฉ 0+16+4+25+36 = 81 ์ 10์ผ๋ก ๋๋ ๋๋จธ์ง์ธ 1์ด ๊ฒ์ฆ์ ์ ๋ ฅ ์ฒซ์งธ ์ค์ ๊ณ ์ ๋ฒํธ์ ์ฒ์ 5์๋ฆฌ์ ์ซ์๋ค์ด ๋น์นธ์ ์ฌ์ด์ ๋๊ณ ํ๋์ฉ ์ฃผ์ด์ง๋ค ์ถ๋ ฅ ์ฒซ์งธ ์ค์ ๊ฒ์ฆ์๋ฅผ ์ถ๋ ฅํ๋ค. // [2475] ๊ฒ์ฆ์ /* ์ปดํจํฐ๋ฅผ ์ ์กฐํ๋ ํ์ฌ์ธ KOI ์ ์์์๋ ์ ์กฐํ๋ ์ปดํจํฐ๋ง๋ค 6์๋ฆฌ์ ๊ณ ์ ๋ฒํธ๋ฅผ ๋งค..
9๊ฐ์ ์๋ก ๋ค๋ฅธ ์์ฐ์๊ฐ ์ฃผ์ด์ง ๋, ์ด๋ค ์ค ์ต๋๊ฐ์ ์ฐพ๊ณ ๊ทธ ์ต๋๊ฐ์ด ๋ช ๋ฒ์งธ ์์ธ์ง๋ฅผ ๊ตฌํ๋ ํ๋ก๊ทธ๋จ์ ์์ฑ ์๋ฅผ ๋ค์ด, ์๋ก ๋ค๋ฅธ 9๊ฐ์ ์์ฐ์ 3, 29, 38, 12, 57, 74, 40, 85, 61 ์ด ์ฃผ์ด์ง๋ฉด, ์ด๋ค ์ค ์ต๋๊ฐ์ 85์ด๊ณ , ์ด ๊ฐ์ 8๋ฒ์งธ ์ ์ ๋ ฅ ์ฒซ์งธ ์ค๋ถํฐ ์ํ ๋ฒ์งธ ์ค๊น์ง ํ ์ค์ ํ๋์ ์์ฐ์๊ฐ ์ฃผ์ด์ง๋ค. ์ฃผ์ด์ง๋ ์์ฐ์๋ 100 ๋ณด๋ค ์๋ค. ์ถ๋ ฅ ์ฒซ์งธ ์ค์ ์ต๋๊ฐ์ ์ถ๋ ฅํ๊ณ , ๋์งธ ์ค์ ์ต๋๊ฐ์ด ๋ช ๋ฒ์งธ ์์ธ์ง๋ฅผ ์ถ๋ ฅ // [2562] ์ต๋๊ฐ /* 9๊ฐ์ ์๋ก ๋ค๋ฅธ ์์ฐ์๊ฐ ์ฃผ์ด์ง ๋, ์ด๋ค ์ค ์ต๋๊ฐ์ ์ฐพ๊ณ ๊ทธ ์ต๋๊ฐ์ด ๋ช ๋ฒ์งธ ์์ธ์ง๋ฅผ ๊ตฌํ๋ ํ๋ก๊ทธ๋จ์ ์์ฑ ์๋ฅผ ๋ค์ด, ์๋ก ๋ค๋ฅธ 9๊ฐ์ ์์ฐ์ 3, 29, 38, 12, 57, 74, 40, 85, 61 ์ด..
์ด๋ค ์์ฐ์ p์ q๊ฐ ์์ ๋, ๋ง์ผ p๋ฅผ q๋ก ๋๋์์ ๋ ๋๋จธ์ง๊ฐ 0์ด๋ฉด q๋ p์ ์ฝ์ ๋ ๊ฐ์ ์์ฐ์ N๊ณผ K๊ฐ ์ฃผ์ด์ก์ ๋, N์ ์ฝ์๋ค ์ค K๋ฒ์งธ๋ก ์์ ์๋ฅผ ์ถ๋ ฅํ๋ ํ๋ก๊ทธ๋จ ์ ๋ ฅ ์ฒซ์งธ ์ค์ N๊ณผ K๊ฐ ๋น์นธ์ ์ฌ์ด์ ๋๊ณ ์ฃผ์ด์ง๋ค. N์ 1 ์ด์ 10,000 ์ดํ์ด๋ค. K๋ 1 ์ด์ N ์ดํ ์ถ๋ ฅ ์ฒซ์งธ ์ค์ N์ ์ฝ์๋ค ์ค K๋ฒ์งธ๋ก ์์ ์๋ฅผ ์ถ๋ ฅํ๋ค. ๋ง์ผ N์ ์ฝ์์ ๊ฐ์๊ฐ K๊ฐ๋ณด๋ค ์ ์ด์ K๋ฒ์งธ ์ฝ์๊ฐ ์กด์ฌํ์ง ์์ ๊ฒฝ์ฐ์๋ 0์ ์ถ๋ ฅ // [2501] ์ฝ์ ๊ตฌํ๊ธฐ /* ์ด๋ค ์์ฐ์ p์ q๊ฐ ์์ ๋, ๋ง์ผ p๋ฅผ q๋ก ๋๋์์ ๋ ๋๋จธ์ง๊ฐ 0์ด๋ฉด q๋ p์ ์ฝ์ ๋ ๊ฐ์ ์์ฐ์ N๊ณผ K๊ฐ ์ฃผ์ด์ก์ ๋, N์ ์ฝ์๋ค ์ค K๋ฒ์งธ๋ก ์์ ์๋ฅผ ์ถ๋ ฅํ๋ ํ๋ก๊ทธ๋จ ์ ๋ ฅ ์ฒซ์งธ ์ค์ N๊ณผ K๊ฐ ..
์์ฐ์ M๊ณผ N์ด ์ฃผ์ด์ง ๋ M์ด์ N์ดํ์ ์์ฐ์ ์ค ์์์ธ ๊ฒ์ ๋ชจ๋ ๊ณจ๋ผ ์ด๋ค ์์์ ํฉ๊ณผ ์ต์๊ฐ์ ์ฐพ๋ ํ๋ก๊ทธ๋จ์ ์์ฑ ์ ๋ ฅ ์ ๋ ฅ์ ์ฒซ์งธ ์ค์ M์ด, ๋์งธ ์ค์ N์ด ์ฃผ์ด์ง๋ค. M๊ณผ N์ 10,000์ดํ์ ์์ฐ์์ด๋ฉฐ, M์ N๋ณด๋ค ์๊ฑฐ๋ ๊ฐ๋ค. ์ถ๋ ฅ M์ด์ N์ดํ์ ์์ฐ์ ์ค ์์์ธ ๊ฒ์ ๋ชจ๋ ์ฐพ์ ์ฒซ์งธ ์ค์ ๊ทธ ํฉ์, ๋์งธ ์ค์ ๊ทธ ์ค ์ต์๊ฐ์ ์ถ๋ ฅํ๋ค. ๋จ, M์ด์ N์ดํ์ ์์ฐ์ ์ค ์์๊ฐ ์์ ๊ฒฝ์ฐ๋ ์ฒซ์งธ ์ค์ -1์ ์ถ๋ ฅ // [2581] ์์ /* ์์ฐ์ M๊ณผ N์ด ์ฃผ์ด์ง ๋ M์ด์ N์ดํ์ ์์ฐ์ ์ค ์์์ธ ๊ฒ์ ๋ชจ๋ ๊ณจ๋ผ ์ด๋ค ์์์ ํฉ๊ณผ ์ต์๊ฐ์ ์ฐพ๋ ํ๋ก๊ทธ๋จ์ ์์ฑ ์ ๋ ฅ ์ ๋ ฅ์ ์ฒซ์งธ ์ค์ M์ด, ๋์งธ ์ค์ N์ด ์ฃผ์ด์ง๋ค. M๊ณผ N์ 10,000์ดํ์ ์์ฐ์์ด๋ฉฐ, M์ N๋ณด๋ค ์๊ฑฐ..
์ฃผ์ด์ง ์ N๊ฐ ์ค์์ ์์๊ฐ ๋ช ๊ฐ์ธ์ง ์ฐพ์์ ์ถ๋ ฅํ๋ ํ๋ก๊ทธ๋จ์ ์์ฑ ์ ๋ ฅ ์ฒซ ์ค์ ์์ ๊ฐ์ N์ด ์ฃผ์ด์ง๋ค. N์ 100์ดํ์ด๋ค. ๋ค์์ผ๋ก N๊ฐ์ ์๊ฐ ์ฃผ์ด์ง๋๋ฐ ์๋ 1,000 ์ดํ์ ์์ฐ์ ์ถ๋ ฅ ์ฃผ์ด์ง ์๋ค ์ค ์์์ ๊ฐ์๋ฅผ ์ถ๋ ฅ // [1978] ์์ ์ฐพ๊ธฐ /* ์ฃผ์ด์ง ์ N๊ฐ ์ค์์ ์์๊ฐ ๋ช ๊ฐ์ธ์ง ์ฐพ์์ ์ถ๋ ฅํ๋ ํ๋ก๊ทธ๋จ์ ์์ฑ ์ ๋ ฅ ์ฒซ ์ค์ ์์ ๊ฐ์ N์ด ์ฃผ์ด์ง๋ค. N์ 100์ดํ์ด๋ค. ๋ค์์ผ๋ก N๊ฐ์ ์๊ฐ ์ฃผ์ด์ง๋๋ฐ ์๋ 1,000 ์ดํ์ ์์ฐ์ ์ถ๋ ฅ ์ฃผ์ด์ง ์๋ค ์ค ์์์ ๊ฐ์๋ฅผ ์ถ๋ ฅ */ #define _CRT_SECURE_NO_WARNINGS // ํ์ค ์คํธ๋ฆผ์์ ์ฝ๊ธฐ ๋ฐ ์ฐ๊ธฐ๋ฅผ ์ ์ดํ๋ ๊ฐ์ฒด๋ฅผ ์ ์ธ #include #include using namespace std; int ..