๋ณธ๋ฌธ ๋ฐ”๋กœ๊ฐ€๊ธฐ
728x90
๋ฐ˜์‘ํ˜•

๋ฐฑ์ค€์ฝ”๋”ฉํ…Œ์ŠคํŠธ5

[Python] ๋ฐฑ์ค€ 2292๋ฒˆ ๋ฒŒ์ง‘ - ๊ตฌํ˜„ ๋ฐฑ์ค€ ํ™ˆํŽ˜์ด์ง€ ๋ฌธ์ œ์™€ ๊ฐœ์ธ์ ์ธ ํ’€์ด๋ฅผ ์ž‘์„ฑํ•œ ๊ธ€์ž…๋‹ˆ๋‹ค. ๋ฐฑ์ค€ 2292๋ฒˆ : ๋ฒŒ์ง‘ 2292๋ฒˆ: ๋ฒŒ์ง‘ ์œ„์˜ ๊ทธ๋ฆผ๊ณผ ๊ฐ™์ด ์œก๊ฐํ˜•์œผ๋กœ ์ด๋ฃจ์–ด์ง„ ๋ฒŒ์ง‘์ด ์žˆ๋‹ค. ๊ทธ๋ฆผ์—์„œ ๋ณด๋Š” ๋ฐ”์™€ ๊ฐ™์ด ์ค‘์•™์˜ ๋ฐฉ 1๋ถ€ํ„ฐ ์‹œ์ž‘ํ•ด์„œ ์ด์›ƒํ•˜๋Š” ๋ฐฉ์— ๋Œ์•„๊ฐ€๋ฉด์„œ 1์”ฉ ์ฆ๊ฐ€ํ•˜๋Š” ๋ฒˆํ˜ธ๋ฅผ ์ฃผ์†Œ๋กœ ๋งค๊ธธ ์ˆ˜ ์žˆ๋‹ค. ์ˆซ์ž N์ด ์ฃผ์–ด์กŒ www.acmicpc.net ๋ฌธ์ œ ์œ„์˜ ๊ทธ๋ฆผ๊ณผ ๊ฐ™์ด ์œก๊ฐํ˜•์œผ๋กœ ์ด๋ฃจ์–ด์ง„ ๋ฒŒ์ง‘์ด ์žˆ๋‹ค. ๊ทธ๋ฆผ์—์„œ ๋ณด๋Š” ๋ฐ”์™€ ๊ฐ™์ด ์ค‘์•™์˜ ๋ฐฉ 1๋ถ€ํ„ฐ ์‹œ์ž‘ํ•ด์„œ ์ด์›ƒํ•˜๋Š” ๋ฐฉ์— ๋Œ์•„๊ฐ€๋ฉด์„œ 1์”ฉ ์ฆ๊ฐ€ํ•˜๋Š” ๋ฒˆํ˜ธ๋ฅผ ์ฃผ์†Œ๋กœ ๋งค๊ธธ ์ˆ˜ ์žˆ๋‹ค. ์ˆซ์ž N ์ด ์ฃผ์–ด์กŒ์„ ๋•Œ, ๋ฒŒ์ง‘์˜ ์ค‘์•™ 1์—์„œ N๋ฒˆ ๋ฐฉ๊นŒ์ง€ ์ตœ์†Œ ๊ฐœ์ˆ˜์˜ ๋ฐฉ์„ ์ง€๋‚˜์„œ ๊ฐˆ ๋•Œ ๋ช‡ ๊ฐœ์˜ ๋ฐฉ์„ ์ง€๋‚˜๊ฐ€๋Š”์ง€(์‹œ์ž‘๊ณผ ๋์„ ํฌํ•จํ•˜์—ฌ)๋ฅผ ๊ณ„์‚ฐํ•˜๋Š” ํ”„๋กœ๊ทธ๋žจ์„ ์ž‘์„ฑํ•˜์‹œ์˜ค. ์˜ˆ๋ฅผ ๋“ค๋ฉด, 13๊นŒ์ง€๋Š” 3๊ฐœ, 58๊นŒ์ง€๋Š” .. 2023. 3. 17.
[Python] ๋ฐฑ์ค€ 1157๋ฒˆ ๋‹จ์–ด ๊ณต๋ถ€ - ๊ตฌํ˜„ ๋ฐฑ์ค€ ํ™ˆํŽ˜์ด์ง€ ๋ฌธ์ œ์™€ ๊ฐœ์ธ์ ์ธ ํ’€์ด๋ฅผ ์ž‘์„ฑํ•œ ๊ธ€์ž…๋‹ˆ๋‹ค. ๋ฐฑ์ค€ 1157๋ฒˆ : ๋‹จ์–ด ๊ณต๋ถ€ 1157๋ฒˆ: ๋‹จ์–ด ๊ณต๋ถ€ ์•ŒํŒŒ๋ฒณ ๋Œ€์†Œ๋ฌธ์ž๋กœ ๋œ ๋‹จ์–ด๊ฐ€ ์ฃผ์–ด์ง€๋ฉด, ์ด ๋‹จ์–ด์—์„œ ๊ฐ€์žฅ ๋งŽ์ด ์‚ฌ์šฉ๋œ ์•ŒํŒŒ๋ฒณ์ด ๋ฌด์—‡์ธ์ง€ ์•Œ์•„๋‚ด๋Š” ํ”„๋กœ๊ทธ๋žจ์„ ์ž‘์„ฑํ•˜์‹œ์˜ค. ๋‹จ, ๋Œ€๋ฌธ์ž์™€ ์†Œ๋ฌธ์ž๋ฅผ ๊ตฌ๋ถ„ํ•˜์ง€ ์•Š๋Š”๋‹ค. www.acmicpc.net ๋ฌธ์ œ ์•ŒํŒŒ๋ฒณ ๋Œ€์†Œ๋ฌธ์ž๋กœ ๋œ ๋‹จ์–ด๊ฐ€ ์ฃผ์–ด์ง€๋ฉด, ์ด ๋‹จ์–ด์—์„œ ๊ฐ€์žฅ ๋งŽ์ด ์‚ฌ์šฉ๋œ ์•ŒํŒŒ๋ฒณ์ด ๋ฌด์—‡์ธ์ง€ ์•Œ์•„๋‚ด๋Š” ํ”„๋กœ๊ทธ๋žจ์„ ์ž‘์„ฑํ•˜์‹œ์˜ค. ๋‹จ, ๋Œ€๋ฌธ์ž์™€ ์†Œ๋ฌธ์ž๋ฅผ ๊ตฌ๋ถ„ํ•˜์ง€ ์•Š๋Š”๋‹ค. ์ž…๋ ฅ ์ฒซ์งธ ์ค„์— ์•ŒํŒŒ๋ฒณ ๋Œ€์†Œ๋ฌธ์ž๋กœ ์ด๋ฃจ์–ด์ง„ ๋‹จ์–ด๊ฐ€ ์ฃผ์–ด์ง„๋‹ค. ์ฃผ์–ด์ง€๋Š” ๋‹จ์–ด์˜ ๊ธธ์ด๋Š” 1,000,000์„ ๋„˜์ง€ ์•Š๋Š”๋‹ค. ์ถœ๋ ฅ ์ฒซ์งธ ์ค„์— ์ด ๋‹จ์–ด์—์„œ ๊ฐ€์žฅ ๋งŽ์ด ์‚ฌ์šฉ๋œ ์•ŒํŒŒ๋ฒณ์„ ๋Œ€๋ฌธ์ž๋กœ ์ถœ๋ ฅํ•œ๋‹ค. ๋‹จ, ๊ฐ€์žฅ ๋งŽ์ด ์‚ฌ์šฉ๋œ ์•ŒํŒŒ๋ฒณ์ด ์—ฌ๋Ÿฌ ๊ฐœ ์กด์žฌํ•˜๋Š” ๊ฒฝ์šฐ.. 2023. 3. 16.
[Python] ๋ฐฑ์ค€ 10655๋ฒˆ ๋งˆ๋ผํ†ค 1 - ๊ตฌํ˜„ ๋ฐฑ์ค€ ํ™ˆํŽ˜์ด์ง€ ๋ฌธ์ œ์™€ ๊ฐœ์ธ์ ์ธ ํ’€์ด๋ฅผ ์ž‘์„ฑํ•œ ๊ธ€์ž…๋‹ˆ๋‹ค. ๋ฐฑ์ค€ 10655๋ฒˆ : ๋งˆ๋ผํ†ค 1 10655๋ฒˆ: ๋งˆ๋ผํ†ค 1 ์ –์†Œ ๋ฐ•์Šน์›์€ 2๋ฒˆ์งธ ํ˜น์€ 3๋ฒˆ์งธ ์ฒดํฌํฌ์ธํŠธ๋ฅผ ๊ฑด๋„ˆ๋›ธ ์ˆ˜ ์žˆ๋Š”๋ฐ, ์—ฌ๊ธฐ์„œ ๋‘ ๋ฒˆ์งธ ์ฒดํฌํฌ์ธํŠธ๋ฅผ ๊ฑด๋„ˆ๋›ธ ๊ฒฝ์šฐ ๊ฒฝ๋กœ๋Š” (0,0) -> (11,-1) -> (10,0) ์ด ๋˜๋ฉฐ ๊ฑฐ๋ฆฌ๋Š” 14์ด๋‹ค. ๋ฐ•์Šน์›์€ ์ด๊ฒƒ๋ณด๋‹ค ๋” ์งง๊ฒŒ ๋‹ฌ๋ฆด www.acmicpc.net ๋ฌธ์ œ ๋†์žฅ์— ์žˆ๋Š” ์ –์†Œ๋“ค์ด ๊ฑด๊ฐ•ํ•˜์ง€ ๋ชปํ•˜๋‹ค๊ณ  ์ƒ๊ฐํ•œ ๋†๋ถ€ ์กด์€ ์ –์†Œ๋“ค์„ ์œ„ํ•œ ๋งˆ๋ผํ†ค ๋Œ€ํšŒ๋ฅผ ์—ด์—ˆ๊ณ , ๋†๋ถ€ ์กด์˜ ์ด์• ๋ฅผ ๋ฐ›๋Š” ์ –์†Œ ๋ฐ•์Šน์› ์—ญ์‹œ ์ด ๋Œ€ํšŒ์— ์ฐธ๊ฐ€ํ•  ์˜ˆ์ •์ด๋‹ค. ๋งˆ๋ผํ†ค ์ฝ”์Šค๋Š” N (3 โ‰ค N โ‰ค 100000) ๊ฐœ์˜ ์ฒดํฌํฌ์ธํŠธ๋กœ ๊ตฌ์„ฑ๋˜์–ด ์žˆ์œผ๋ฉฐ, 1๋ฒˆ ์ฒดํฌํฌ์ธํŠธ์—์„œ ์‹œ์ž‘ํ•ด์„œ ๋ชจ๋“  ์ฒดํฌ ํฌ์ธํŠธ๋ฅผ ์ˆœ์„œ๋Œ€๋กœ ๋ฐฉ๋ฌธํ•œ ํ›„ N๋ฒˆ ์ฒดํฌํฌ์ธํŠธ์—์„œ ๋๋‚˜์•ผ์ง€.. 2023. 3. 14.
[Python] ๋ฐฑ์ค€ 1439๋ฒˆ ๋’ค์ง‘๊ธฐ - ๊ทธ๋ฆฌ๋”” ์•Œ๊ณ ๋ฆฌ์ฆ˜ ๋ฐฑ์ค€ ํ™ˆํŽ˜์ด์ง€ ๋ฌธ์ œ์™€ ๊ฐœ์ธ์ ์ธ ํ’€์ด๋ฅผ ์ž‘์„ฑํ•œ ๊ธ€์ž…๋‹ˆ๋‹ค. ๋ฐฑ์ค€ 1439๋ฒˆ : ๋’ค์ง‘๊ธฐ 1439๋ฒˆ: ๋’ค์ง‘๊ธฐ ๋‹ค์†œ์ด๋Š” 0๊ณผ 1๋กœ๋งŒ ์ด๋ฃจ์–ด์ง„ ๋ฌธ์ž์—ด S๋ฅผ ๊ฐ€์ง€๊ณ  ์žˆ๋‹ค. ๋‹ค์†œ์ด๋Š” ์ด ๋ฌธ์ž์—ด S์— ์žˆ๋Š” ๋ชจ๋“  ์ˆซ์ž๋ฅผ ์ „๋ถ€ ๊ฐ™๊ฒŒ ๋งŒ๋“ค๋ ค๊ณ  ํ•œ๋‹ค. ๋‹ค์†œ์ด๊ฐ€ ํ•  ์ˆ˜ ์žˆ๋Š” ํ–‰๋™์€ S์—์„œ ์—ฐ์†๋œ ํ•˜๋‚˜ ์ด์ƒ์˜ ์ˆซ์ž๋ฅผ ์žก๊ณ  ๋ชจ www.acmicpc.net ๋ฌธ์ œ ๋‹ค์†œ์ด๋Š” 0๊ณผ 1๋กœ๋งŒ ์ด๋ฃจ์–ด์ง„ ๋ฌธ์ž์—ด S๋ฅผ ๊ฐ€์ง€๊ณ  ์žˆ๋‹ค. ๋‹ค์†œ์ด๋Š” ์ด ๋ฌธ์ž์—ด S์— ์žˆ๋Š” ๋ชจ๋“  ์ˆซ์ž๋ฅผ ์ „๋ถ€ ๊ฐ™๊ฒŒ ๋งŒ๋“ค๋ ค๊ณ  ํ•œ๋‹ค. ๋‹ค์†œ์ด๊ฐ€ ํ•  ์ˆ˜ ์žˆ๋Š” ํ–‰๋™์€ S์—์„œ ์—ฐ์†๋œ ํ•˜๋‚˜ ์ด์ƒ์˜ ์ˆซ์ž๋ฅผ ์žก๊ณ  ๋ชจ๋‘ ๋’ค์ง‘๋Š” ๊ฒƒ์ด๋‹ค. ๋’ค์ง‘๋Š” ๊ฒƒ์€ 1์„ 0์œผ๋กœ, 0์„ 1๋กœ ๋ฐ”๊พธ๋Š” ๊ฒƒ์„ ์˜๋ฏธํ•œ๋‹ค. ์˜ˆ๋ฅผ ๋“ค์–ด S=0001100 ์ผ ๋•Œ, ์ „์ฒด๋ฅผ ๋’ค์ง‘์œผ๋ฉด 1110011์ด ๋œ๋‹ค. 4๋ฒˆ์งธ ๋ฌธ์ž๋ถ€ํ„ฐ 5๋ฒˆ์งธ .. 2023. 3. 10.
[Python] ๋ฐฑ์ค€ 11880๋ฒˆ ๊ฐœ๋ฏธ - ๊ธฐํ•˜ํ•™(geometry) ๋ฐฑ์ค€ ํ™ˆํŽ˜์ด์ง€ ๋ฌธ์ œ์™€ ๊ฐœ์ธ์ ์ธ ํ’€์ด๋ฅผ ์ž‘์„ฑํ•œ ๊ธ€์ž…๋‹ˆ๋‹ค. ๋ฐฑ์ค€ 11880๋ฒˆ : ๊ฐœ๋ฏธ 11880๋ฒˆ: ๊ฐœ๋ฏธ ์Šนํ˜„์ด๋Š” ๋ฐฉํ•™์„ ๋งž์•„ ์‹ฌ์‹ฌํ•˜์ง€๋งŒ, ๊ณต๋ถ€๋Š” ํ•˜๊ธฐ ์‹ซ์Šต๋‹ˆ๋‹ค. ์ด๋ ‡๊ฒŒ ๋ฐฉ ์•ˆ์—์„œ ํ•˜๋ฃจํ•˜๋ฃจ ์‹œ๊ฐ„์„ ๋‚ญ๋น„ํ•˜๋˜ ์ค‘, ์Šนํ˜„์ด๋Š” ์ž์‹ ์˜ ์ง์œก๋ฉด์ฒด ๋ชจ์–‘์˜ ์ง€์šฐ๊ฐœ์— ๊ฐœ๋ฏธ ํ•œ ๋งˆ๋ฆฌ๊ฐ€ ๋ถ™์–ด ์žˆ๋‹ค๋Š” ๊ฒƒ์„ ์•Œ๊ฒŒ www.acmicpc.net ๋ฌธ์ œ ์Šนํ˜„์ด๋Š” ๋ฐฉํ•™์„ ๋งž์•„ ์‹ฌ์‹ฌํ•˜์ง€๋งŒ, ๊ณต๋ถ€๋Š” ํ•˜๊ธฐ ์‹ซ์Šต๋‹ˆ๋‹ค. ์ด๋ ‡๊ฒŒ ๋ฐฉ ์•ˆ์—์„œ ํ•˜๋ฃจํ•˜๋ฃจ ์‹œ๊ฐ„์„ ๋‚ญ๋น„ํ•˜๋˜ ์ค‘, ์Šนํ˜„์ด๋Š” ์ž์‹ ์˜ ์ง์œก๋ฉด์ฒด ๋ชจ์–‘์˜ ์ง€์šฐ๊ฐœ์— ๊ฐœ๋ฏธ ํ•œ ๋งˆ๋ฆฌ๊ฐ€ ๋ถ™์–ด ์žˆ๋‹ค๋Š” ๊ฒƒ์„ ์•Œ๊ฒŒ ๋ฉ๋‹ˆ๋‹ค. ์‚ฌ์‹ค ์ด ๊ฐœ๋ฏธ๋Š” ์šฐ๋ฆฌ๊ฐ€ ๋ฌธ์ œ๋ฅผ ์–ด๋–ป๊ฒŒ ๋‚ผ ์ง€ ์ž˜ ๋ชฐ๋ผ์„œ ๋ฐฉ์— ๋„ฃ์€ ๋กœ๋ด‡์ž…๋‹ˆ๋‹ค. ์ด ๊ฐœ๋ฏธ ๋กœ๋ด‡์€ ๋ง๋„ ์•ˆ ๋˜์ง€๋งŒ ์–ด๋– ํ•œ ์‹œ๋ จ์ด ๋‹ฅ์ณ๋„ ์„œ๋กœ ๋ฐ˜๋Œ€ํŽธ์— ์œ„์น˜ํ•œ ์  A์—์„œ ์  B๊นŒ์ง€ ์ตœ๋‹จ ๊ฑฐ๋ฆฌ๋กœ ์ด๋™ํ•˜๋ฉฐ.. 2023. 3. 9.
728x90
๋ฐ˜์‘ํ˜•