๋ชฉ๋ก์ „์ฒด ๊ธ€ (1005)

๐Ÿ˜Ž ๊ณต๋ถ€ํ•˜๋Š” ์ง•์ง•์•ŒํŒŒ์นด๋Š” ์ฒ˜์Œ์ด์ง€?

[BAEKJOON C++] 2490_์œท๋†€์ด

์šฐ๋ฆฌ๋‚˜๋ผ ๊ณ ์œ ์˜ ์œท๋†€์ด๋Š” ๋„ค ๊ฐœ์˜ ์œท์ง์„ ๋˜์ ธ์„œ ๋ฐฐ(0)์™€ ๋“ฑ(1)์ด ๋‚˜์˜ค๋Š” ์ˆซ์ž๋ฅผ ์„ธ์–ด ๋„, ๊ฐœ, ๊ฑธ, ์œท, ๋ชจ๋ฅผ ๊ฒฐ์ •ํ•œ๋‹ค ๋„ค ๊ฐœ ์œท์ง์„ ๋˜์ ธ์„œ ๋‚˜์˜จ ๊ฐ ์œท์ง์˜ ๋ฐฐ ํ˜น์€ ๋“ฑ ์ •๋ณด๊ฐ€ ์ฃผ์–ด์งˆ ๋•Œ ๋„(๋ฐฐ ํ•œ ๊ฐœ, ๋“ฑ ์„ธ ๊ฐœ), ๊ฐœ(๋ฐฐ ๋‘ ๊ฐœ, ๋“ฑ ๋‘ ๊ฐœ), ๊ฑธ(๋ฐฐ ์„ธ ๊ฐœ, ๋“ฑ ํ•œ ๊ฐœ), ์œท(๋ฐฐ ๋„ค ๊ฐœ), ๋ชจ(๋“ฑ ๋„ค ๊ฐœ) ์ค‘ ์–ด๋–ค ๊ฒƒ์ธ์ง€๋ฅผ ๊ฒฐ์ •ํ•˜๋Š” ํ”„๋กœ๊ทธ๋žจ์„ ์ž‘์„ฑ ์ž…๋ ฅ ์ฒซ์งธ ์ค„๋ถ€ํ„ฐ ์…‹์งธ ์ค„๊นŒ์ง€ ๊ฐ ์ค„์— ๊ฐ๊ฐ ํ•œ ๋ฒˆ ๋˜์ง„ ์œท์ง๋“ค์˜ ์ƒํƒœ๋ฅผ ๋‚˜ํƒ€๋‚ด๋Š” ๋„ค ๊ฐœ์˜ ์ •์ˆ˜(0 ๋˜๋Š” 1)๊ฐ€ ๋นˆ์นธ์„ ์‚ฌ์ด์— ๋‘๊ณ  ์ฃผ์–ด์ง„๋‹ค. ์ถœ๋ ฅ ์ฒซ์งธ ์ค„๋ถ€ํ„ฐ ์…‹์งธ ์ค„๊นŒ์ง€ ํ•œ ์ค„์— ํ•˜๋‚˜์”ฉ ๊ฒฐ๊ณผ๋ฅผ ๋„๋Š” A, ๊ฐœ๋Š” B, ๊ฑธ์€ C, ์œท์€ D, ๋ชจ๋Š” E๋กœ ์ถœ๋ ฅํ•œ๋‹ค // [2490] ์œท๋†€์ด /* ์šฐ๋ฆฌ๋‚˜๋ผ ๊ณ ์œ ์˜ ์œท๋†€์ด๋Š” ๋„ค ๊ฐœ์˜ ์œท์ง์„ ๋˜์ ธ์„œ ๋ฐฐ(0)์™€ ๋“ฑ..

[BAEKJOON C++] 2747_ํ”ผ๋ณด๋‚˜์น˜ ์ˆ˜

ํ”ผ๋ณด๋‚˜์น˜ ์ˆ˜๋Š” 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๋ฒˆ์งธ ํ”ผ๋ณด๋‚˜์น˜ ์ˆ˜๋Š”..

[BAEKJOON C++] 2475_๊ฒ€์ฆ์ˆ˜

์ปดํ“จํ„ฐ๋ฅผ ์ œ์กฐํ•˜๋Š” ํšŒ์‚ฌ์ธ KOI ์ „์ž์—์„œ๋Š” ์ œ์กฐํ•˜๋Š” ์ปดํ“จํ„ฐ๋งˆ๋‹ค 6์ž๋ฆฌ์˜ ๊ณ ์œ ๋ฒˆํ˜ธ๋ฅผ ๋งค๊ธด๋‹ค. ๊ณ ์œ ๋ฒˆํ˜ธ์˜ ์ฒ˜์Œ 5์ž๋ฆฌ์—๋Š” 00000๋ถ€ํ„ฐ 99999๊นŒ์ง€์˜ ์ˆ˜ ์ค‘ ํ•˜๋‚˜๊ฐ€ ์ฃผ์–ด์ง€๋ฉฐ 6๋ฒˆ์งธ ์ž๋ฆฌ์—๋Š” ๊ฒ€์ฆ์ˆ˜๊ฐ€ ๋“ค์–ด๊ฐ„๋‹ค. ๊ฒ€์ฆ์ˆ˜๋Š” ๊ณ ์œ ๋ฒˆํ˜ธ์˜ ์ฒ˜์Œ 5์ž๋ฆฌ์— ๋“ค์–ด๊ฐ€๋Š” 5๊ฐœ์˜ ์ˆซ์ž๋ฅผ ๊ฐ๊ฐ ์ œ๊ณฑํ•œ ์ˆ˜์˜ ํ•ฉ์„ 10์œผ๋กœ ๋‚˜๋ˆˆ ๋‚˜๋จธ์ง€์ด๋‹ค. ์˜ˆ๋ฅผ ๋“ค์–ด ๊ณ ์œ ๋ฒˆํ˜ธ์˜ ์ฒ˜์Œ 5์ž๋ฆฌ์˜ ์ˆซ์ž๋“ค์ด 04256์ด๋ฉด, ๊ฐ ์ˆซ์ž๋ฅผ ์ œ๊ณฑํ•œ ์ˆ˜๋“ค์˜ ํ•ฉ 0+16+4+25+36 = 81 ์„ 10์œผ๋กœ ๋‚˜๋ˆˆ ๋‚˜๋จธ์ง€์ธ 1์ด ๊ฒ€์ฆ์ˆ˜ ์ž…๋ ฅ ์ฒซ์งธ ์ค„์— ๊ณ ์œ ๋ฒˆํ˜ธ์˜ ์ฒ˜์Œ 5์ž๋ฆฌ์˜ ์ˆซ์ž๋“ค์ด ๋นˆ์นธ์„ ์‚ฌ์ด์— ๋‘๊ณ  ํ•˜๋‚˜์”ฉ ์ฃผ์–ด์ง„๋‹ค ์ถœ๋ ฅ ์ฒซ์งธ ์ค„์— ๊ฒ€์ฆ์ˆ˜๋ฅผ ์ถœ๋ ฅํ•œ๋‹ค. // [2475] ๊ฒ€์ฆ์ˆ˜ /* ์ปดํ“จํ„ฐ๋ฅผ ์ œ์กฐํ•˜๋Š” ํšŒ์‚ฌ์ธ KOI ์ „์ž์—์„œ๋Š” ์ œ์กฐํ•˜๋Š” ์ปดํ“จํ„ฐ๋งˆ๋‹ค 6์ž๋ฆฌ์˜ ๊ณ ์œ ๋ฒˆํ˜ธ๋ฅผ ๋งค..

[BAEKJOON C++] 2562_์ตœ๋Œ“๊ฐ’

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 ์ด..

[BAEKJOON C++] 2501_์•ฝ์ˆ˜ ๊ตฌํ•˜๊ธฐ

์–ด๋–ค ์ž์—ฐ์ˆ˜ 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๊ฐ€ ..

[BAEKJOON C++] 2581_์†Œ์ˆ˜

์ž์—ฐ์ˆ˜ 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๋ณด๋‹ค ์ž‘๊ฑฐ..

[BAEKJOON C++] 1978_์†Œ์ˆ˜ ์ฐพ๊ธฐ

์ฃผ์–ด์ง„ ์ˆ˜ 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 ..