์ฝ”๋”ฉํ…Œ์ŠคํŠธ 14

[๋ฐฑ์ค€ 2583] ์˜์—ญ ๊ตฌํ•˜๊ธฐ

๋ฌธ์ œ 2583๋ฒˆ: ์˜์—ญ ๊ตฌํ•˜๊ธฐ ์ฒซ์งธ ์ค„์— M๊ณผ N, ๊ทธ๋ฆฌ๊ณ  K๊ฐ€ ๋นˆ์นธ์„ ์‚ฌ์ด์— ๋‘๊ณ  ์ฐจ๋ก€๋กœ ์ฃผ์–ด์ง„๋‹ค. M, N, K๋Š” ๋ชจ๋‘ 100 ์ดํ•˜์˜ ์ž์—ฐ์ˆ˜์ด๋‹ค. ๋‘˜์งธ ์ค„๋ถ€ํ„ฐ K๊ฐœ์˜ ์ค„์—๋Š” ํ•œ ์ค„์— ํ•˜๋‚˜์”ฉ ์ง์‚ฌ๊ฐํ˜•์˜ ์™ผ์ชฝ ์•„๋ž˜ ๊ผญ์ง“์ ์˜ x, y์ขŒํ‘œ๊ฐ’๊ณผ ์˜ค www.acmicpc.net ๋ˆˆ๊ธˆ์˜ ๊ฐ„๊ฒฉ์ด 1์ธ M×N(M,N≤100)ํฌ๊ธฐ์˜ ๋ชจ๋ˆˆ์ข…์ด๊ฐ€ ์žˆ๋‹ค. ์ด ๋ชจ๋ˆˆ์ข…์ด ์œ„์— ๋ˆˆ๊ธˆ์— ๋งž์ถ”์–ด K๊ฐœ์˜ ์ง์‚ฌ๊ฐํ˜•์„ ๊ทธ๋ฆด ๋•Œ, ์ด๋“ค K๊ฐœ์˜ ์ง์‚ฌ๊ฐํ˜•์˜ ๋‚ด๋ถ€๋ฅผ ์ œ์™ธํ•œ ๋‚˜๋จธ์ง€ ๋ถ€๋ถ„์ด ๋ช‡ ๊ฐœ์˜ ๋ถ„๋ฆฌ๋œ ์˜์—ญ์œผ๋กœ ๋‚˜๋ˆ„์–ด์ง„๋‹ค. ์˜ˆ๋ฅผ ๋“ค์–ด M=5, N=7 ์ธ ๋ชจ๋ˆˆ์ข…์ด ์œ„์— ๊ณผ ๊ฐ™์ด ์ง์‚ฌ๊ฐํ˜• 3๊ฐœ๋ฅผ ๊ทธ๋ ธ๋‹ค๋ฉด, ๊ทธ ๋‚˜๋จธ์ง€ ์˜์—ญ์€ ์™€ ๊ฐ™์ด 3๊ฐœ์˜ ๋ถ„๋ฆฌ๋œ ์˜์—ญ์œผ๋กœ ๋‚˜๋ˆ„์–ด์ง€๊ฒŒ ๋œ๋‹ค. M, N๊ณผ K ๊ทธ๋ฆฌ๊ณ  K๊ฐœ์˜ ์ง์‚ฌ๊ฐํ˜•์˜ ์ขŒํ‘œ๊ฐ€ ์ฃผ์–ด์งˆ ๋•Œ, K๊ฐœ์˜ ์ง์‚ฌ๊ฐํ˜• ..

Algorithm 2023.05.11

[๋ฐฑ์ค€ 2468] ์•ˆ์ „ ์˜์—ญ

๋ฌธ์ œ 2468๋ฒˆ: ์•ˆ์ „ ์˜์—ญ ์žฌ๋‚œ๋ฐฉ์žฌ์ฒญ์—์„œ๋Š” ๋งŽ์€ ๋น„๊ฐ€ ๋‚ด๋ฆฌ๋Š” ์žฅ๋งˆ์ฒ ์— ๋Œ€๋น„ํ•ด์„œ ๋‹ค์Œ๊ณผ ๊ฐ™์€ ์ผ์„ ๊ณ„ํšํ•˜๊ณ  ์žˆ๋‹ค. ๋จผ์ € ์–ด๋–ค ์ง€์—ญ์˜ ๋†’์ด ์ •๋ณด๋ฅผ ํŒŒ์•…ํ•œ๋‹ค. ๊ทธ ๋‹ค์Œ์— ๊ทธ ์ง€์—ญ์— ๋งŽ์€ ๋น„๊ฐ€ ๋‚ด๋ ธ์„ ๋•Œ ๋ฌผ์— ์ž ๊ธฐ์ง€ ์•Š๋Š” www.acmicpc.net ์žฌ๋‚œ๋ฐฉ์žฌ์ฒญ์—์„œ๋Š” ๋งŽ์€ ๋น„๊ฐ€ ๋‚ด๋ฆฌ๋Š” ์žฅ๋งˆ์ฒ ์— ๋Œ€๋น„ํ•ด์„œ ๋‹ค์Œ๊ณผ ๊ฐ™์€ ์ผ์„ ๊ณ„ํšํ•˜๊ณ  ์žˆ๋‹ค. ๋จผ์ € ์–ด๋–ค ์ง€์—ญ์˜ ๋†’์ด ์ •๋ณด๋ฅผ ํŒŒ์•…ํ•œ๋‹ค. ๊ทธ ๋‹ค์Œ์— ๊ทธ ์ง€์—ญ์— ๋งŽ์€ ๋น„๊ฐ€ ๋‚ด๋ ธ์„ ๋•Œ ๋ฌผ์— ์ž ๊ธฐ์ง€ ์•Š๋Š” ์•ˆ์ „ํ•œ ์˜์—ญ์ด ์ตœ๋Œ€๋กœ ๋ช‡ ๊ฐœ๊ฐ€ ๋งŒ๋“ค์–ด ์ง€๋Š” ์ง€๋ฅผ ์กฐ์‚ฌํ•˜๋ ค๊ณ  ํ•œ๋‹ค. ์ด๋•Œ, ๋ฌธ์ œ๋ฅผ ๊ฐ„๋‹จํ•˜๊ฒŒ ํ•˜๊ธฐ ์œ„ํ•˜์—ฌ, ์žฅ๋งˆ์ฒ ์— ๋‚ด๋ฆฌ๋Š” ๋น„์˜ ์–‘์— ๋”ฐ๋ผ ์ผ์ •ํ•œ ๋†’์ด ์ดํ•˜์˜ ๋ชจ๋“  ์ง€์ ์€ ๋ฌผ์— ์ž ๊ธด๋‹ค๊ณ  ๊ฐ€์ •ํ•œ๋‹ค. ์–ด๋–ค ์ง€์—ญ์˜ ๋†’์ด ์ •๋ณด๊ฐ€ ์ฃผ์–ด์กŒ์„ ๋•Œ, ์žฅ๋งˆ์ฒ ์— ๋ฌผ์— ์ž ๊ธฐ์ง€ ์•Š๋Š” ์•ˆ์ „ํ•œ ์˜์—ญ์˜ ์ตœ๋Œ€ ..

Algorithm 2023.05.10

[๋ฐฑ์ค€ 1012] ์œ ๊ธฐ๋† ๋ฐฐ์ถ”

๋ฌธ์ œ 1012๋ฒˆ: ์œ ๊ธฐ๋† ๋ฐฐ์ถ” ์ฐจ์„ธ๋Œ€ ์˜๋†์ธ ํ•œ๋‚˜๋Š” ๊ฐ•์›๋„ ๊ณ ๋žญ์ง€์—์„œ ์œ ๊ธฐ๋† ๋ฐฐ์ถ”๋ฅผ ์žฌ๋ฐฐํ•˜๊ธฐ๋กœ ํ•˜์˜€๋‹ค. ๋†์•ฝ์„ ์“ฐ์ง€ ์•Š๊ณ  ๋ฐฐ์ถ”๋ฅผ ์žฌ๋ฐฐํ•˜๋ ค๋ฉด ๋ฐฐ์ถ”๋ฅผ ํ•ด์ถฉ์œผ๋กœ๋ถ€ํ„ฐ ๋ณดํ˜ธํ•˜๋Š” ๊ฒƒ์ด ์ค‘์š”ํ•˜๊ธฐ ๋•Œ๋ฌธ์—, ํ•œ๋‚˜๋Š” ํ•ด์ถฉ ๋ฐฉ์ง€์— www.acmicpc.net ์ฐจ์„ธ๋Œ€ ์˜๋†์ธ ํ•œ๋‚˜๋Š” ๊ฐ•์›๋„ ๊ณ ๋žญ์ง€์—์„œ ์œ ๊ธฐ๋† ๋ฐฐ์ถ”๋ฅผ ์žฌ๋ฐฐํ•˜๊ธฐ๋กœ ํ•˜์˜€๋‹ค. ๋†์•ฝ์„ ์“ฐ์ง€ ์•Š๊ณ  ๋ฐฐ์ถ”๋ฅผ ์žฌ๋ฐฐํ•˜๋ ค๋ฉด ๋ฐฐ์ถ”๋ฅผ ํ•ด์ถฉ์œผ๋กœ๋ถ€ํ„ฐ ๋ณดํ˜ธํ•˜๋Š” ๊ฒƒ์ด ์ค‘์š”ํ•˜๊ธฐ ๋•Œ๋ฌธ์—, ํ•œ๋‚˜๋Š” ํ•ด์ถฉ ๋ฐฉ์ง€์— ํšจ๊ณผ์ ์ธ ๋ฐฐ์ถ”ํฐ์ง€๋ ์ด๋ฅผ ๊ตฌ์ž…ํ•˜๊ธฐ๋กœ ๊ฒฐ์‹ฌํ•œ๋‹ค. ์ด ์ง€๋ ์ด๋Š” ๋ฐฐ์ถ”๊ทผ์ฒ˜์— ์„œ์‹ํ•˜๋ฉฐ ํ•ด์ถฉ์„ ์žก์•„ ๋จน์Œ์œผ๋กœ์จ ๋ฐฐ์ถ”๋ฅผ ๋ณดํ˜ธํ•œ๋‹ค. ํŠนํžˆ, ์–ด๋–ค ๋ฐฐ์ถ”์— ๋ฐฐ์ถ”ํฐ์ง€๋ ์ด๊ฐ€ ํ•œ ๋งˆ๋ฆฌ๋ผ๋„ ์‚ด๊ณ  ์žˆ์œผ๋ฉด ์ด ์ง€๋ ์ด๋Š” ์ธ์ ‘ํ•œ ๋‹ค๋ฅธ ๋ฐฐ์ถ”๋กœ ์ด๋™ํ•  ์ˆ˜ ์žˆ์–ด, ๊ทธ ๋ฐฐ์ถ”๋“ค ์—ญ์‹œ ํ•ด์ถฉ์œผ๋กœ๋ถ€ํ„ฐ ๋ณดํ˜ธ๋ฐ›์„ ์ˆ˜ ์žˆ๋‹ค. ํ•œ ๋ฐฐ์ถ”์˜ ์ƒํ•˜์ขŒ..

Algorithm 2023.05.08

[๋ฐฑ์ค€ 4375] 1

๋ฌธ์ œ 4375๋ฒˆ: 1 2์™€ 5๋กœ ๋‚˜๋ˆ„์–ด ๋–จ์–ด์ง€์ง€ ์•Š๋Š” ์ •์ˆ˜ n(1 ≤ n ≤ 10000)๊ฐ€ ์ฃผ์–ด์กŒ์„ ๋•Œ, 1๋กœ๋งŒ ์ด๋ฃจ์–ด์ง„ n์˜ ๋ฐฐ์ˆ˜๋ฅผ ์ฐพ๋Š” ํ”„๋กœ๊ทธ๋žจ์„ ์ž‘์„ฑํ•˜์‹œ์˜ค. www.acmicpc.net 2์™€ 5๋กœ ๋‚˜๋ˆ„์–ด ๋–จ์–ด์ง€์ง€ ์•Š๋Š” ์ •์ˆ˜ n(1 ≤ n ≤ 10000)๊ฐ€ ์ฃผ์–ด์กŒ์„ ๋•Œ, 1๋กœ๋งŒ ์ด๋ฃจ์–ด์ง„ n์˜ ๋ฐฐ์ˆ˜๋ฅผ ์ฐพ๋Š” ํ”„๋กœ๊ทธ๋žจ์„ ์ž‘์„ฑํ•˜์‹œ์˜ค. ์ž…๋ ฅ์€ ์—ฌ๋Ÿฌ ๊ฐœ์˜ ํ…Œ์ŠคํŠธ ์ผ€์ด์Šค๋กœ ์ด๋ฃจ์–ด์ ธ ์žˆ๋‹ค. ๊ฐ ํ…Œ์ŠคํŠธ ์ผ€์ด์Šค๋Š” ํ•œ ์ค„๋กœ ์ด๋ฃจ์–ด์ ธ ์žˆ๊ณ , n์ด ์ฃผ์–ด์ง„๋‹ค. 1๋กœ ์ด๋ฃจ์–ด์ง„ n์˜ ๋ฐฐ์ˆ˜ ์ค‘ ๊ฐ€์žฅ ์ž‘์€ ์ˆ˜์˜ ์ž๋ฆฌ์ˆ˜๋ฅผ ์ถœ๋ ฅํ•œ๋‹ค. ํ’€์ด ๊ณต์œ  ์†Œ์Šค ๋ณด๊ธฐ www.acmicpc.net ์•„์ด๋””์–ด 1 ๋ถ€ํ„ฐ cnt ๊นŒ์ง€ n ์œผ๋กœ ๊ณ„์† ๋‚˜๋ˆ„๋Š” ๊ฒƒ์€ cnt ์˜ ์‹œ๊ฐ„ ๋ณต์žก๋„๊ฐ€ ๋ฐœ์ƒํ•ด ์‹œ๊ฐ„ ์ดˆ๊ณผ๊ฐ€ ๋ฐœ์ƒํ•œ๋‹ค. ์ตœ๋Œ€ ์ž…๋ ฅ๊ฐ’์ธ 9999 ์„ 1 ๋ถ€ํ„ฐ cnt..

Algorithm 2023.04.23

[๋ฐฑ์ค€ 3986] ์ข‹์€ ๋‹จ์–ด

๋ฌธ์ œ 3986๋ฒˆ: ์ข‹์€ ๋‹จ์–ด ์ด๋ฒˆ ๊ณ„์ ˆํ•™๊ธฐ์— ์‹ฌ๋ฆฌํ•™ ๊ฐœ๋ก ์„ ์ˆ˜๊ฐ• ์ค‘์ธ ํ‰์„์ด๋Š” ์˜ค๋Š˜ ์ž์ •๊นŒ์ง€ ๋ณด๊ณ ์„œ๋ฅผ ์ œ์ถœํ•ด์•ผ ํ•œ๋‹ค. ๋ณด๊ณ ์„œ ์ž‘์„ฑ์ด ๋„ˆ๋ฌด ์ง€๋ฃจํ–ˆ๋˜ ํ‰์„์ด๋Š” ๋…ธํŠธ๋ถ์— ์—Ž๋“œ๋ ค์„œ ๊พธ๋ฒ…๊พธ๋ฒ… ์กธ๋‹ค๊ฐ€ ์ œ์ถœ ๋งˆ๊ฐ 1์‹œ๊ฐ„ ์ „์— www.acmicpc.net ์ด๋ฒˆ ๊ณ„์ ˆํ•™๊ธฐ์— ์‹ฌ๋ฆฌํ•™ ๊ฐœ๋ก ์„ ์ˆ˜๊ฐ• ์ค‘์ธ ํ‰์„์ด๋Š” ์˜ค๋Š˜ ์ž์ •๊นŒ์ง€ ๋ณด๊ณ ์„œ๋ฅผ ์ œ์ถœํ•ด์•ผ ํ•œ๋‹ค. ๋ณด๊ณ ์„œ ์ž‘์„ฑ์ด ๋„ˆ๋ฌด ์ง€๋ฃจํ–ˆ๋˜ ํ‰์„์ด๋Š” ๋…ธํŠธ๋ถ์— ์—Ž๋“œ๋ ค์„œ ๊พธ๋ฒ…๊พธ๋ฒ… ์กธ๋‹ค๊ฐ€ ์ œ์ถœ ๋งˆ๊ฐ 1์‹œ๊ฐ„ ์ „์— ๊นจ๊ณ  ๋ง์•˜๋‹ค. ์•ˆํƒ€๊น๊ฒŒ๋„ ์ž๋Š” ๋™์•ˆ ํ‚ค๋ณด๋“œ๊ฐ€ ์ž˜๋ชป ๋ˆŒ๋ ค์„œ ๋ณด๊ณ ์„œ์˜ ๋ชจ๋“  ๊ธ€์ž๊ฐ€ A์™€ B๋กœ ๋ฐ”๋€Œ์–ด ๋ฒ„๋ ธ๋‹ค! ๊ทธ๋ž˜์„œ ํ‰์„์ด๋Š” ๋ณด๊ณ ์„œ ์ž‘์„ฑ์„ ๋•Œ๋ ค์น˜์šฐ๊ณ  ๋ณด๊ณ ์„œ์—์„œ '์ข‹์€ ๋‹จ์–ด'๋‚˜ ์„ธ๋ณด๊ธฐ๋กœ ๋งˆ์Œ ๋จน์—ˆ๋‹ค. ํ‰์„์ด๋Š” ๋‹จ์–ด ์œ„๋กœ ์•„์น˜ํ˜• ๊ณก์„ ์„ ๊ทธ์–ด ๊ฐ™์€ ๊ธ€์ž๋ผ๋ฆฌ(A๋Š” A๋ผ๋ฆฌ, B๋Š” B๋ผ๋ฆฌ) ์Œ์„ ์ง“..

Algorithm 2023.04.18

[๋ฐฑ์ค€ 1940] ์ฃผ๋ชฝ

๋ฌธ์ œ 1940๋ฒˆ: ์ฃผ๋ชฝ ์ฒซ์งธ ์ค„์—๋Š” ์žฌ๋ฃŒ์˜ ๊ฐœ์ˆ˜ N(1 ≤ N ≤ 15,000)์ด ์ฃผ์–ด์ง„๋‹ค. ๊ทธ๋ฆฌ๊ณ  ๋‘ ๋ฒˆ์งธ ์ค„์—๋Š” ๊ฐ‘์˜ท์„ ๋งŒ๋“œ๋Š”๋ฐ ํ•„์š”ํ•œ ์ˆ˜ M(1 ≤ M ≤ 10,000,000) ์ฃผ์–ด์ง„๋‹ค. ๊ทธ๋ฆฌ๊ณ  ๋งˆ์ง€๋ง‰์œผ๋กœ ์…‹์งธ ์ค„์—๋Š” N๊ฐœ์˜ ์žฌ๋ฃŒ๋“ค์ด ๊ฐ€์ง„ ๊ณ  www.acmicpc.net ์ฃผ๋ชฝ์€ ์ฒ ๊ธฐ๊ตฐ์„ ์–‘์„ฑํ•˜๊ธฐ ์œ„ํ•œ ํ”„๋กœ์ ํŠธ์— ๋‚˜์„ฐ๋‹ค. ๊ทธ๋ž˜์„œ ์•ผ์ฒ ๋Œ€์žฅ์„ ํ†ตํ•ด ์ฒ ๊ธฐ๊ตฐ์ด ์ž…์„ ๊ฐ‘์˜ท์„ ๋งŒ๋“ค๊ฒŒ ํ•˜์˜€๋‹ค. ์•ผ์ฒ ๋Œ€์žฅ์€ ์ฃผ๋ชฝ์˜ ๋ช…์— ๋”ฐ๋ฅด๊ธฐ ์œ„ํ•˜์—ฌ ์—ฐ๊ตฌ์— ์ฐฉ์ˆ˜ํ•˜๋˜ ์ค‘ ์•„๋ž˜์™€ ๊ฐ™์€ ์‚ฌ์‹ค์„ ๋ฐœ๊ฒฌํ•˜๊ฒŒ ๋˜์—ˆ๋‹ค. ๊ฐ‘์˜ท์„ ๋งŒ๋“œ๋Š” ์žฌ๋ฃŒ๋“ค์€ ๊ฐ๊ฐ ๊ณ ์œ ํ•œ ๋ฒˆํ˜ธ๋ฅผ ๊ฐ€์ง€๊ณ  ์žˆ๋‹ค. ๊ฐ‘์˜ท์€ ๋‘ ๊ฐœ์˜ ์žฌ๋ฃŒ๋กœ ๋งŒ๋“œ๋Š”๋ฐ ๋‘ ์žฌ๋ฃŒ์˜ ๊ณ ์œ ํ•œ ๋ฒˆํ˜ธ๋ฅผ ํ•ฉ์ณ์„œ M(1 ≤ M ≤ 10,000,000)์ด ๋˜๋ฉด ๊ฐ‘์˜ท์ด ๋งŒ๋“ค์–ด ์ง€๊ฒŒ ๋œ๋‹ค. ์•ผ์ฒ ๋Œ€์žฅ์€ ์ž์‹ ์ด ๋งŒ๋“ค๊ณ  ์žˆ๋Š” ์žฌ๋ฃŒ..

Algorithm 2023.04.17

[๋ฐฑ์ค€ 1213] ํŒฐ๋ฆฐ๋“œ๋กฌ ๋งŒ๋“ค๊ธฐ

๋ฌธ์ œ ๋ฐฑ์ค€ 1213 ์ž„ํ•œ์ˆ˜์™€ ์ž„๋ฌธ๋นˆ์€ ์„œ๋กœ ์‚ฌ๋ž‘ํ•˜๋Š” ์‚ฌ์ด์ด๋‹ค. ์ž„ํ•œ์ˆ˜๋Š” ์„ธ์ƒ์—์„œ ํŒฐ๋ฆฐ๋“œ๋กฌ์ธ ๋ฌธ์ž์—ด์„ ๋„ˆ๋ฌด ์ข‹์•„ํ•˜๊ธฐ ๋•Œ๋ฌธ์—, ๋‘˜์˜ ๋ฐฑ์ผ์„ ๊ธฐ๋…ํ•ด์„œ ์ž„๋ฌธ๋นˆ์€ ํŒฐ๋ฆฐ๋“œ๋กฌ์„ ์„ ๋ฌผํ•ด์ฃผ๋ ค๊ณ  ํ•œ๋‹ค. ์ž„๋ฌธ๋นˆ์€ ์ž„ํ•œ์ˆ˜์˜ ์˜์–ด ์ด๋ฆ„์œผ๋กœ ํŒฐ๋ฆฐ๋“œ๋กฌ์„ ๋งŒ๋“ค๋ ค๊ณ  ํ•˜๋Š”๋ฐ, ์ž„ํ•œ์ˆ˜์˜ ์˜์–ด ์ด๋ฆ„์˜ ์•ŒํŒŒ๋ฒณ ์ˆœ์„œ๋ฅผ ์ ์ ˆํžˆ ๋ฐ”๊ฟ”์„œ ํŒฐ๋ฆฐ๋“œ๋กฌ์„ ๋งŒ๋“ค๋ ค๊ณ  ํ•œ๋‹ค. ์ž„๋ฌธ๋นˆ์„ ๋„์™€ ์ž„ํ•œ์ˆ˜์˜ ์˜์–ด ์ด๋ฆ„์„ ํŒฐ๋ฆฐ๋“œ๋กฌ์œผ๋กœ ๋ฐ”๊พธ๋Š” ํ”„๋กœ๊ทธ๋žจ์„ ์ž‘์„ฑํ•˜์‹œ์˜ค. ์ฒซ์งธ ์ค„์— ์ž„ํ•œ์ˆ˜์˜ ์˜์–ด ์ด๋ฆ„์ด ์žˆ๋‹ค. ์•ŒํŒŒ๋ฒณ ๋Œ€๋ฌธ์ž๋กœ๋งŒ ๋œ ์ตœ๋Œ€ 50๊ธ€์ž์ด๋‹ค. ์ฒซ์งธ ์ค„์— ๋ฌธ์ œ์˜ ์ •๋‹ต์„ ์ถœ๋ ฅํ•œ๋‹ค. ๋งŒ์•ฝ ๋ถˆ๊ฐ€๋Šฅํ•  ๋•Œ๋Š” "I'm Sorry Hansoo"๋ฅผ ์ถœ๋ ฅํ•œ๋‹ค. ์ •๋‹ต์ด ์—ฌ๋Ÿฌ ๊ฐœ์ผ ๊ฒฝ์šฐ์—๋Š” ์‚ฌ์ „์ˆœ์œผ๋กœ ์•ž์„œ๋Š” ๊ฒƒ์„ ์ถœ๋ ฅํ•œ๋‹ค. ํ’€์ด ์ œ์ถœํ•œ ์ฝ”๋“œ ์•„์ด๋””์–ด ํŒฐ๋ฆฐ๋“œ๋กฌ์œผ๋กœ ๋งŒ๋“ค ์ˆ˜ ์žˆ๋Š” ๊ฒฝ์šฐ ์ž…..

Algorithm 2023.04.16

[๋ฐฑ์ค€ 1620] ๋‚˜๋Š”์•ผ ํฌ์ผ“๋ชฌ ๋งˆ์Šคํ„ฐ ์ด๋‹ค์†œ

๋ฌธ์ œ 1620๋ฒˆ: ๋‚˜๋Š”์•ผ ํฌ์ผ“๋ชฌ ๋งˆ์Šคํ„ฐ ์ด๋‹ค์†œ ์ฒซ์งธ ์ค„์—๋Š” ๋„๊ฐ์— ์ˆ˜๋ก๋˜์–ด ์žˆ๋Š” ํฌ์ผ“๋ชฌ์˜ ๊ฐœ์ˆ˜ N์ด๋ž‘ ๋‚ด๊ฐ€ ๋งž์ถฐ์•ผ ํ•˜๋Š” ๋ฌธ์ œ์˜ ๊ฐœ์ˆ˜ M์ด ์ฃผ์–ด์ ธ. N๊ณผ M์€ 1๋ณด๋‹ค ํฌ๊ฑฐ๋‚˜ ๊ฐ™๊ณ , 100,000๋ณด๋‹ค ์ž‘๊ฑฐ๋‚˜ ๊ฐ™์€ ์ž์—ฐ์ˆ˜์ธ๋ฐ, ์ž์—ฐ์ˆ˜๊ฐ€ ๋ญ”์ง€๋Š” ์•Œ์ง€? ๋ชจ๋ฅด๋ฉด www.acmicpc.net ์ฒซ์งธ ์ค„์—๋Š” ๋„๊ฐ์— ์ˆ˜๋ก๋˜์–ด ์žˆ๋Š” ํฌ์ผ“๋ชฌ์˜ ๊ฐœ์ˆ˜ N์ด๋ž‘ ๋‚ด๊ฐ€ ๋งž์ถฐ์•ผ ํ•˜๋Š” ๋ฌธ์ œ์˜ ๊ฐœ์ˆ˜ M์ด ์ฃผ์–ด์ ธ. N๊ณผ M์€ 1๋ณด๋‹ค ํฌ๊ฑฐ๋‚˜ ๊ฐ™๊ณ , 100,000๋ณด๋‹ค ์ž‘๊ฑฐ๋‚˜ ๊ฐ™์€ ์ž์—ฐ์ˆ˜์ธ๋ฐ, ์ž์—ฐ์ˆ˜๊ฐ€ ๋ญ”์ง€๋Š” ์•Œ์ง€? ๋ชจ๋ฅด๋ฉด ๋ฌผ์–ด๋ด๋„ ๊ดœ์ฐฎ์•„. ๋‚˜๋Š” ์–ธ์ œ๋“ ์ง€ ์งˆ๋ฌธ์— ๋‹ตํ•ด์ค„ ์ค€๋น„๊ฐ€ ๋˜์–ด์žˆ์–ด. ๋‘˜์งธ ์ค„๋ถ€ํ„ฐ N๊ฐœ์˜ ์ค„์— ํฌ์ผ“๋ชฌ์˜ ๋ฒˆํ˜ธ๊ฐ€ 1๋ฒˆ์ธ ํฌ์ผ“๋ชฌ๋ถ€ํ„ฐ N๋ฒˆ์— ํ•ด๋‹นํ•˜๋Š” ํฌ์ผ“๋ชฌ๊นŒ์ง€ ํ•œ ์ค„์— ํ•˜๋‚˜์”ฉ ์ž…๋ ฅ์œผ๋กœ ๋“ค์–ด์™€. ํฌ์ผ“๋ชฌ์˜ ์ด๋ฆ„์€ ๋ชจ๋‘ ์˜์–ด๋กœ๋งŒ ์ด๋ฃจ์–ด์ ธ์žˆ๊ณ ..

Algorithm 2023.04.12

[๋ฐฑ์ค€ 9996] ํ•œ๊ตญ์ด ๊ทธ๋ฆฌ์šธ ๋• ์„œ๋ฒ„์— ์ ‘์†ํ•˜์ง€

๋ฌธ์ œ 9996๋ฒˆ: ํ•œ๊ตญ์ด ๊ทธ๋ฆฌ์šธ ๋• ์„œ๋ฒ„์— ์ ‘์†ํ•˜์ง€ ์ด N๊ฐœ์˜ ์ค„์— ๊ฑธ์ณ์„œ, ์ž…๋ ฅ์œผ๋กœ ์ฃผ์–ด์ง„ i๋ฒˆ์งธ ํŒŒ์ผ ์ด๋ฆ„์ด ํŒจํ„ด๊ณผ ์ผ์น˜ํ•˜๋ฉด "DA", ์ผ์น˜ํ•˜์ง€ ์•Š์œผ๋ฉด "NE"๋ฅผ ์ถœ๋ ฅํ•œ๋‹ค. ์ฐธ๊ณ ๋กœ, "DA"๋Š” ํฌ๋กœ์•„ํ‹ฐ์–ด์–ด๋กœ "YES"๋ฅผ, "NE"๋Š” "NO"๋ฅผ ์˜๋ฏธํ•œ๋‹ค. www.acmicpc.net ํ’€์ด ์‹คํŒจํ•œ ์ฝ”๋“œ ๋กœ๊ทธ์ธ www.acmicpc.net ์•„์ด๋””์–ด ์ฃผ์–ด์ง„ ํŒจํ„ด์—์„œ * ๊ฐ€ ์œ„์น˜ํ•œ ์ธ๋ฑ์Šค ๋ฒˆํ˜ธ๋ฅผ ์ฐพ๋Š”๋‹ค. ์ž…๋ ฅํ•œ ํŒŒ์ผ๋ช…์˜ prefix ์™€ suffix ๋ฅผ ์ถ”์ถœํ•œ๋‹ค. ํŒจํ„ด๊ณผ ๋Œ€์กฐํ•œ ๊ฒฐ๊ณผ๋ฅผ ์ถœ๋ ฅํ•œ๋‹ค. ๋ฌธ์ œ์  substr() ๋ฅผ ์‚ฌ์šฉํ•˜์ง€ ์•Š๊ณ  ๋ฌด๋ถ„๋ณ„ํ•œ ๋ฐ˜๋ณต๋ฌธ ์‚ฌ์šฉํ•œ ๊ฒƒ find() ๋ฅผ ์‚ฌ์šฉํ•˜์ง€ ์•Š๊ณ  ๋ฐ˜๋ณต๋ฌธ์„ ์‚ฌ์šฉํ•ด * ์˜ ์œ„์น˜๋ฅผ ์ฐพ์€ ๊ฒƒ ํŒŒ์ผ๋ช…์˜ ๊ธธ์ด๊ฐ€ ํŒจํ„ด์˜ prefix ์™€ suffix ์˜ ๊ธธ์ด ํ•ฉ๋ณด๋‹ค ์ž‘์€ ๊ฒฝ์šฐ๋ฅผ ..

Algorithm 2023.04.04

[๋ฐฑ์ค€ 10988] ํŒฐ๋ฆฐ๋“œ๋กฌ์ธ์ง€ ํ™•์ธํ•˜๊ธฐ

๋ฌธ์ œ 10988๋ฒˆ: ํŒฐ๋ฆฐ๋“œ๋กฌ์ธ์ง€ ํ™•์ธํ•˜๊ธฐ ์ฒซ์งธ ์ค„์— ๋‹จ์–ด๊ฐ€ ์ฃผ์–ด์ง„๋‹ค. ๋‹จ์–ด์˜ ๊ธธ์ด๋Š” 1๋ณด๋‹ค ํฌ๊ฑฐ๋‚˜ ๊ฐ™๊ณ , 100๋ณด๋‹ค ์ž‘๊ฑฐ๋‚˜ ๊ฐ™์œผ๋ฉฐ, ์•ŒํŒŒ๋ฒณ ์†Œ๋ฌธ์ž๋กœ๋งŒ ์ด๋ฃจ์–ด์ ธ ์žˆ๋‹ค. www.acmicpc.net ํ’€์ด ์ž…๋ ฅํ•œ ๋ฌธ์ž์—ด์„ ๋ฐ˜์œผ๋กœ ๋‚˜๋ˆ„๊ณ , ์•ž ๋ถ€๋ถ„๊ณผ ์ด๋ฅผ ๋’ค์ง‘์€ ๊ณณ์— ์œ„์น˜ํ•œ ๊ฐ’์„ ๋น„๊ตํ•˜๋Š” ๋ฐฉ๋ฒ• #include using namespace std; int solve(string str) { int center = (str.length() / 2) + (str.length() % 2); // ์ค‘๊ฐ„์˜ ์ „๋ฉด๊ณผ ํ›„๋ฉด์„ ๋น„๊ต for (int i = 0; i < center; i++) { int j = str.length() - i - 1; if (str[i] != str[j]) return 0; } return 1; } ..

Algorithm 2023.03.29