Algorithm/๐Ÿ‘ ๋ฌธ์ œ

๋ฏธ๋กœํƒ์ƒ‰ ๐Ÿช™ N×Mํฌ๊ธฐ์˜ ๋ฐฐ์—ด๋กœ ํ‘œํ˜„๋˜๋Š” ๋ฏธ๋กœ๊ฐ€ ์žˆ๋‹ค. ๋ฏธ๋กœ์—์„œ 1์€ ์ด๋™ํ•  ์ˆ˜ ์žˆ๋Š” ์นธ์„ ๋‚˜ํƒ€๋‚ด๊ณ , 0์€ ์ด๋™ํ•  ์ˆ˜ ์—†๋Š” ์นธ์„ ๋‚˜ํƒ€๋‚ธ๋‹ค. ์ด๋Ÿฌํ•œ ๋ฏธ๋กœ๊ฐ€ ์ฃผ์–ด์กŒ์„ ๋•Œ, (1, 1)์—์„œ ์ถœ๋ฐœํ•˜์—ฌ (N, M)์˜ ์œ„์น˜๋กœ ์ด๋™ํ•  ๋•Œ ์ง€๋‚˜์•ผ ํ•˜๋Š” ์ตœ์†Œ์˜ ์นธ ์ˆ˜๋ฅผ ๊ตฌํ•˜๋Š” ํ”„๋กœ๊ทธ๋žจ์„ ์ž‘์„ฑํ•˜์‹œ์˜ค. ํ•œ ์นธ์—์„œ ๋‹ค๋ฅธ ์นธ์œผ๋กœ ์ด๋™ํ•  ๋•Œ, ์„œ๋กœ ์ธ์ ‘ํ•œ ์นธ์œผ๋กœ๋งŒ ์ด๋™ํ•  ์ˆ˜ ์žˆ๋‹ค. ์œ„์˜ ์˜ˆ์—์„œ๋Š” 15์นธ์„ ์ง€๋‚˜์•ผ (N, M)์˜ ์œ„์น˜๋กœ ์ด๋™ํ•  ์ˆ˜ ์žˆ๋‹ค. ์นธ์„ ์…€ ๋•Œ์—๋Š” ์‹œ์ž‘ ์œ„์น˜์™€ ๋„์ฐฉ ์œ„์น˜๋„ ํฌํ•จํ•œ๋‹ค. ์ž…๋ ฅ ์ฒซ์งธ ์ค„์— ๋‘ ์ •์ˆ˜ N, M(2 ≤ N, M ≤ 100)์ด ์ฃผ์–ด์ง„๋‹ค. ๋‹ค์Œ N๊ฐœ์˜ ์ค„์—๋Š” M๊ฐœ์˜ ์ •์ˆ˜๋กœ ๋ฏธ๋กœ๊ฐ€ ์ฃผ์–ด์ง„๋‹ค. ๊ฐ๊ฐ์˜ ์ˆ˜๋“ค์€ ๋ถ™์–ด์„œ ์ž…๋ ฅ์œผ๋กœ ์ฃผ์–ด์ง„๋‹ค. ์ถœ๋ ฅ ์ฒซ์งธ ์ค„์— ์ง€๋‚˜์•ผ ํ•˜๋Š” ์ตœ์†Œ์˜ ์นธ ์ˆ˜๋ฅผ ์ถœ๋ ฅํ•œ๋‹ค. ํ•ญ์ƒ ๋„..
๊ทธ๋ฆผ ๐Ÿช™ ์–ด๋–ค ํฐ ๋„ํ™”์ง€์— ๊ทธ๋ฆผ์ด ๊ทธ๋ ค์ ธ ์žˆ์„ ๋•Œ, ๊ทธ ๊ทธ๋ฆผ์˜ ๊ฐœ์ˆ˜์™€, ๊ทธ ๊ทธ๋ฆผ ์ค‘ ๋„“์ด๊ฐ€ ๊ฐ€์žฅ ๋„“์€ ๊ฒƒ์˜ ๋„“์ด๋ฅผ ์ถœ๋ ฅํ•˜์—ฌ๋ผ. ๋‹จ, ๊ทธ๋ฆผ์ด๋ผ๋Š” ๊ฒƒ์€ 1๋กœ ์—ฐ๊ฒฐ๋œ ๊ฒƒ์„ ํ•œ ๊ทธ๋ฆผ์ด๋ผ๊ณ  ์ •์˜ํ•˜์ž. ๊ฐ€๋กœ๋‚˜ ์„ธ๋กœ๋กœ ์—ฐ๊ฒฐ๋œ ๊ฒƒ์€ ์—ฐ๊ฒฐ์ด ๋œ ๊ฒƒ์ด๊ณ  ๋Œ€๊ฐ์„ ์œผ๋กœ ์—ฐ๊ฒฐ์ด ๋œ ๊ฒƒ์€ ๋–จ์–ด์ง„ ๊ทธ๋ฆผ์ด๋‹ค. ๊ทธ๋ฆผ์˜ ๋„“์ด๋ž€ ๊ทธ๋ฆผ์— ํฌํ•จ๋œ 1์˜ ๊ฐœ์ˆ˜์ด๋‹ค. ์ž…๋ ฅ ์ฒซ์งธ ์ค„์— ๋„ํ™”์ง€์˜ ์„ธ๋กœ ํฌ๊ธฐ n(1 ≤ n ≤ 500)๊ณผ ๊ฐ€๋กœ ํฌ๊ธฐ m(1 ≤ m ≤ 500)์ด ์ฐจ๋ก€๋กœ ์ฃผ์–ด์ง„๋‹ค. ๋‘ ๋ฒˆ์งธ ์ค„๋ถ€ํ„ฐ n+1 ์ค„ ๊นŒ์ง€ ๊ทธ๋ฆผ์˜ ์ •๋ณด๊ฐ€ ์ฃผ์–ด์ง„๋‹ค. (๋‹จ ๊ทธ๋ฆผ์˜ ์ •๋ณด๋Š” 0๊ณผ 1์ด ๊ณต๋ฐฑ์„ ๋‘๊ณ  ์ฃผ์–ด์ง€๋ฉฐ, 0์€ ์ƒ‰์น ์ด ์•ˆ๋œ ๋ถ€๋ถ„, 1์€ ์ƒ‰์น ์ด ๋œ ๋ถ€๋ถ„์„ ์˜๋ฏธํ•œ๋‹ค) ์ถœ๋ ฅ ์ฒซ์งธ ์ค„์—๋Š” ๊ทธ๋ฆผ์˜ ๊ฐœ์ˆ˜, ๋‘˜์งธ ์ค„์—๋Š” ๊ทธ ์ค‘ ๊ฐ€์žฅ ๋„“์€ ๊ทธ๋ฆผ์˜ ๋„“์ด๋ฅผ ์ถœ๋ ฅํ•˜์—ฌ๋ผ. ๋‹จ, ..
์ง•๊ฒ€๋‹ค๋ฆฌ๊ฑด๋„ˆ๊ธฐ ์นด์นด์˜ค ์ดˆ๋“ฑํ•™๊ต์˜ "๋‹ˆ๋‹ˆ์ฆˆ ์นœ๊ตฌ๋“ค"์ด "๋ผ์ด์–ธ" ์„ ์ƒ๋‹˜๊ณผ ํ•จ๊ป˜ ๊ฐ€์„ ์†Œํ’์„ ๊ฐ€๋Š” ์ค‘์— ์ง•๊ฒ€๋‹ค๋ฆฌ๊ฐ€ ์žˆ๋Š” ๊ฐœ์šธ์„ ๋งŒ๋‚˜์„œ ๊ฑด๋„ˆํŽธ์œผ๋กœ ๊ฑด๋„ˆ๋ ค๊ณ  ํ•ฉ๋‹ˆ๋‹ค. "๋ผ์ด์–ธ" ์„ ์ƒ๋‹˜์€ "๋‹ˆ๋‹ˆ์ฆˆ ์นœ๊ตฌ๋“ค"์ด ๋ฌด์‚ฌํžˆ ์ง•๊ฒ€๋‹ค๋ฆฌ๋ฅผ ๊ฑด๋„ ์ˆ˜ ์žˆ๋„๋ก ๋‹ค์Œ๊ณผ ๊ฐ™์ด ๊ทœ์น™์„ ๋งŒ๋“ค์—ˆ์Šต๋‹ˆ๋‹ค. ์ง•๊ฒ€๋‹ค๋ฆฌ๋Š” ์ผ๋ ฌ๋กœ ๋†“์—ฌ ์žˆ๊ณ  ๊ฐ ์ง•๊ฒ€๋‹ค๋ฆฌ์˜ ๋””๋”ค๋Œ์—๋Š” ๋ชจ๋‘ ์ˆซ์ž๊ฐ€ ์ ํ˜€ ์žˆ์œผ๋ฉฐ ๋””๋”ค๋Œ์˜ ์ˆซ์ž๋Š” ํ•œ ๋ฒˆ ๋ฐŸ์„ ๋•Œ๋งˆ๋‹ค 1์”ฉ ์ค„์–ด๋“ญ๋‹ˆ๋‹ค. ๋””๋”ค๋Œ์˜ ์ˆซ์ž๊ฐ€ 0์ด ๋˜๋ฉด ๋” ์ด์ƒ ๋ฐŸ์„ ์ˆ˜ ์—†์œผ๋ฉฐ ์ด๋•Œ๋Š” ๊ทธ ๋‹ค์Œ ๋””๋”ค๋Œ๋กœ ํ•œ๋ฒˆ์— ์—ฌ๋Ÿฌ ์นธ์„ ๊ฑด๋„ˆ ๋›ธ ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค. ๋‹จ, ๋‹ค์Œ์œผ๋กœ ๋ฐŸ์„ ์ˆ˜ ์žˆ๋Š” ๋””๋”ค๋Œ์ด ์—ฌ๋Ÿฌ ๊ฐœ์ธ ๊ฒฝ์šฐ ๋ฌด์กฐ๊ฑด ๊ฐ€์žฅ ๊ฐ€๊นŒ์šด ๋””๋”ค๋Œ๋กœ๋งŒ ๊ฑด๋„ˆ๋›ธ ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค. "๋‹ˆ๋‹ˆ์ฆˆ ์นœ๊ตฌ๋“ค"์€ ๊ฐœ์šธ์˜ ์™ผ์ชฝ์— ์žˆ์œผ๋ฉฐ, ๊ฐœ์šธ์˜ ์˜ค๋ฅธ์ชฝ ๊ฑด๋„ˆํŽธ์— ๋„์ฐฉํ•ด์•ผ ์ง•๊ฒ€๋‹ค๋ฆฌ๋ฅผ ๊ฑด๋„Œ..
ํŒฐ๋ฆฐ๋“œ๋กฌ? (๋ฌธ์ œ_ 10942) ๋ช…์šฐ๋Š” ํ™์ค€์ด์™€ ํ•จ๊ป˜ ํŒฐ๋ฆฐ๋“œ๋กฌ ๋†€์ด๋ฅผ ํ•ด๋ณด๋ ค๊ณ  ํ•œ๋‹ค. ๋จผ์ €, ํ™์ค€์ด๋Š” ์ž์—ฐ์ˆ˜ N๊ฐœ๋ฅผ ์น ํŒ์— ์ ๋Š”๋‹ค. ๊ทธ ๋‹ค์Œ, ๋ช…์šฐ์—๊ฒŒ ์งˆ๋ฌธ์„ ์ด M๋ฒˆ ํ•œ๋‹ค. ๊ฐ ์งˆ๋ฌธ์€ ๋‘ ์ •์ˆ˜ S์™€ E(1 ≤ S ≤ E ≤ N)๋กœ ๋‚˜ํƒ€๋‚ผ ์ˆ˜ ์žˆ์œผ๋ฉฐ, S๋ฒˆ์งธ ์ˆ˜๋ถ€ํ„ฐ E๋ฒˆ์งธ ๊นŒ์ง€ ์ˆ˜๊ฐ€ ํŒฐ๋ฆฐ๋“œ๋กฌ์„ ์ด๋ฃจ๋Š”์ง€๋ฅผ ๋ฌผ์–ด๋ณด๋ฉฐ, ๋ช…์šฐ๋Š” ๊ฐ ์งˆ๋ฌธ์— ๋Œ€ํ•ด ํŒฐ๋ฆฐ๋“œ๋กฌ์ด๋‹ค ๋˜๋Š” ์•„๋‹ˆ๋‹ค๋ฅผ ๋งํ•ด์•ผ ํ•œ๋‹ค. ์˜ˆ๋ฅผ ๋“ค์–ด, ํ™์ค€์ด๊ฐ€ ์น ํŒ์— ์ ์€ ์ˆ˜๊ฐ€ 1, 2, 1, 3, 1, 2, 1๋ผ๊ณ  ํ•˜์ž. S = 1, E = 3์ธ ๊ฒฝ์šฐ 1, 2, 1์€ ํŒฐ๋ฆฐ๋“œ๋กฌ์ด๋‹ค. S = 2, E = 5์ธ ๊ฒฝ์šฐ 2, 1, 3, 1์€ ํŒฐ๋ฆฐ๋“œ๋กฌ์ด ์•„๋‹ˆ๋‹ค. S = 3, E = 3์ธ ๊ฒฝ์šฐ 1์€ ํŒฐ๋ฆฐ๋“œ๋กฌ์ด๋‹ค. S = 5, E = 7์ธ ๊ฒฝ์šฐ 1, 2, 1์€ ํŒฐ๋ฆฐ๋“œ๋กฌ์ด๋‹ค. ์ž..
ํšŒ์ „์ดˆ๋ฐฅ (๋ฌธ์ œ _ 15961) ํšŒ์ „ ์ดˆ๋ฐฅ ์Œ์‹์ ์—๋Š” ํšŒ์ „ํ•˜๋Š” ๋ฒจํŠธ ์œ„์— ์—ฌ๋Ÿฌ ๊ฐ€์ง€ ์ข…๋ฅ˜์˜ ์ดˆ๋ฐฅ์ด ์ ‘์‹œ์— ๋‹ด๊ฒจ ๋†“์—ฌ ์žˆ๊ณ , ์†๋‹˜์€ ์ด ์ค‘์—์„œ ์ž๊ธฐ๊ฐ€ ์ข‹์•„ํ•˜๋Š” ์ดˆ๋ฐฅ์„ ๊ณจ๋ผ์„œ ๋จน๋Š”๋‹ค. ์ดˆ๋ฐฅ์˜ ์ข…๋ฅ˜๋ฅผ ๋ฒˆํ˜ธ๋กœ ํ‘œํ˜„ํ•  ๋•Œ, ๋‹ค์Œ ๊ทธ๋ฆผ์€ ํšŒ์ „ ์ดˆ๋ฐฅ ์Œ์‹์ ์˜ ๋ฒจํŠธ ์ƒํƒœ์˜ ์˜ˆ๋ฅผ ๋ณด์—ฌ์ฃผ๊ณ  ์žˆ๋‹ค. ๋ฒจํŠธ ์œ„์—๋Š” ๊ฐ™์€ ์ข…๋ฅ˜์˜ ์ดˆ๋ฐฅ์ด ๋‘˜ ์ด์ƒ ์žˆ์„ ์ˆ˜ ์žˆ๋‹ค. ์ƒˆ๋กœ ๋ฌธ์„ ์—ฐ ํšŒ์ „ ์ดˆ๋ฐฅ ์Œ์‹์ ์ด ๋ถˆ๊ฒฝ๊ธฐ๋กœ ์˜์—…์ด ์–ด๋ ค์›Œ์„œ, ๋‹ค์Œ๊ณผ ๊ฐ™์ด ๋‘ ๊ฐ€์ง€ ํ–‰์‚ฌ๋ฅผ ํ†ตํ•ด์„œ ๋งค์ƒ์„ ์˜ฌ๋ฆฌ๊ณ ์ž ํ•œ๋‹ค. ์›๋ž˜ ํšŒ์ „ ์ดˆ๋ฐฅ์€ ์†๋‹˜์ด ๋งˆ์Œ๋Œ€๋กœ ์ดˆ๋ฐฅ์„ ๊ณ ๋ฅด๊ณ , ๋จน์€ ์ดˆ๋ฐฅ๋งŒํผ ์‹๋Œ€๋ฅผ ๊ณ„์‚ฐํ•˜์ง€๋งŒ, ๋ฒจํŠธ์˜ ์ž„์˜์˜ ํ•œ ์œ„์น˜๋ถ€ํ„ฐ k๊ฐœ์˜ ์ ‘์‹œ๋ฅผ ์—ฐ์†ํ•ด์„œ ๋จน์„ ๊ฒฝ์šฐ ํ• ์ธ๋œ ์ •์•ก ๊ฐ€๊ฒฉ์œผ๋กœ ์ œ๊ณตํ•œ๋‹ค. ๊ฐ ๊ณ ๊ฐ์—๊ฒŒ ์ดˆ๋ฐฅ์˜ ์ข…๋ฅ˜ ํ•˜๋‚˜๊ฐ€ ์“ฐ์ธ ์ฟ ํฐ์„ ๋ฐœํ–‰ํ•˜๊ณ , 1๋ฒˆ ํ–‰์‚ฌ์— ์ฐธ๊ฐ€ํ•  ๊ฒฝ..
YURI๐Ÿ•๐Ÿ“๐Ÿถ
'Algorithm/๐Ÿ‘ ๋ฌธ์ œ' ์นดํ…Œ๊ณ ๋ฆฌ์˜ ๊ธ€ ๋ชฉ๋ก