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

J

[JAVA] BOJ ๋ฐฑ์ค€ 15683 ๊ฐ์‹œ

https://www.acmicpc.net/problem/15683 15683๋ฒˆ: ๊ฐ์‹œ ์Šคํƒ€ํŠธ๋งํฌ์˜ ์‚ฌ๋ฌด์‹ค์€ 1×1ํฌ๊ธฐ์˜ ์ •์‚ฌ๊ฐํ˜•์œผ๋กœ ๋‚˜๋ˆ„์–ด์ ธ ์žˆ๋Š” N×M ํฌ๊ธฐ์˜ ์ง์‚ฌ๊ฐํ˜•์œผ๋กœ ๋‚˜ํƒ€๋‚ผ ์ˆ˜ ์žˆ๋‹ค. ์‚ฌ๋ฌด์‹ค์—๋Š” ์ด K๊ฐœ์˜ CCTV๊ฐ€ ์„ค์น˜๋˜์–ด์ ธ ์žˆ๋Š”๋ฐ, CCTV๋Š” 5๊ฐ€์ง€ ์ข…๋ฅ˜๊ฐ€ ์žˆ๋‹ค. ๊ฐ CCTV๊ฐ€ ๊ฐ www.acmicpc.net ๋ฌธ์ œ ์Šคํƒ€ํŠธ๋งํฌ์˜ ์‚ฌ๋ฌด์‹ค์€ 1×1ํฌ๊ธฐ์˜ ์ •์‚ฌ๊ฐํ˜•์œผ๋กœ ๋‚˜๋ˆ„์–ด์ ธ ์žˆ๋Š” N×M ํฌ๊ธฐ์˜ ์ง์‚ฌ๊ฐํ˜•์œผ๋กœ ๋‚˜ํƒ€๋‚ผ ์ˆ˜ ์žˆ๋‹ค. ์‚ฌ๋ฌด์‹ค์—๋Š” ์ด K๊ฐœ์˜ CCTV๊ฐ€ ์„ค์น˜๋˜์–ด์ ธ ์žˆ๋Š”๋ฐ, CCTV๋Š” 5๊ฐ€์ง€ ์ข…๋ฅ˜๊ฐ€ ์žˆ๋‹ค. ๊ฐ CCTV๊ฐ€ ๊ฐ์‹œํ•  ์ˆ˜ ์žˆ๋Š” ๋ฐฉ๋ฒ•์€ ๋‹ค์Œ๊ณผ ๊ฐ™๋‹ค. 1๋ฒˆ CCTV๋Š” ํ•œ ์ชฝ ๋ฐฉํ–ฅ๋งŒ ๊ฐ์‹œํ•  ์ˆ˜ ์žˆ๋‹ค. 2๋ฒˆ๊ณผ 3๋ฒˆ์€ ๋‘ ๋ฐฉํ–ฅ์„ ๊ฐ์‹œํ•  ์ˆ˜ ์žˆ๋Š”๋ฐ, 2๋ฒˆ์€ ๊ฐ์‹œํ•˜๋Š” ๋ฐฉํ–ฅ์ด ์„œ๋กœ ๋ฐ˜๋Œ€๋ฐฉํ–ฅ์ด์–ด์•ผ ํ•˜๊ณ ,..

[JAVA] BOJ ๋ฐฑ์ค€ 14891 ํ†ฑ๋‹ˆ๋ฐ”ํ€ด

https://www.acmicpc.net/problem/14891 14891๋ฒˆ: ํ†ฑ๋‹ˆ๋ฐ”ํ€ด ์ฒซ์งธ ์ค„์— 1๋ฒˆ ํ†ฑ๋‹ˆ๋ฐ”ํ€ด์˜ ์ƒํƒœ, ๋‘˜์งธ ์ค„์— 2๋ฒˆ ํ†ฑ๋‹ˆ๋ฐ”ํ€ด์˜ ์ƒํƒœ, ์…‹์งธ ์ค„์— 3๋ฒˆ ํ†ฑ๋‹ˆ๋ฐ”ํ€ด์˜ ์ƒํƒœ, ๋„ท์งธ ์ค„์— 4๋ฒˆ ํ†ฑ๋‹ˆ๋ฐ”ํ€ด์˜ ์ƒํƒœ๊ฐ€ ์ฃผ์–ด์ง„๋‹ค. ์ƒํƒœ๋Š” 8๊ฐœ์˜ ์ •์ˆ˜๋กœ ์ด๋ฃจ์–ด์ ธ ์žˆ๊ณ , 12์‹œ๋ฐฉํ–ฅ๋ถ€ํ„ฐ www.acmicpc.net ๋ฌธ์ œ ์ด 8๊ฐœ์˜ ํ†ฑ๋‹ˆ๋ฅผ ๊ฐ€์ง€๊ณ  ์žˆ๋Š” ํ†ฑ๋‹ˆ๋ฐ”ํ€ด 4๊ฐœ๊ฐ€ ์•„๋ž˜ ๊ทธ๋ฆผ๊ณผ ๊ฐ™์ด ์ผ๋ ฌ๋กœ ๋†“์—ฌ์ ธ ์žˆ๋‹ค. ๋˜, ํ†ฑ๋‹ˆ๋Š” N๊ทน ๋˜๋Š” S๊ทน ์ค‘ ํ•˜๋‚˜๋ฅผ ๋‚˜ํƒ€๋‚ด๊ณ  ์žˆ๋‹ค. ํ†ฑ๋‹ˆ๋ฐ”ํ€ด์—๋Š” ๋ฒˆํ˜ธ๊ฐ€ ๋งค๊ฒจ์ ธ ์žˆ๋Š”๋ฐ, ๊ฐ€์žฅ ์™ผ์ชฝ ํ†ฑ๋‹ˆ๋ฐ”ํ€ด๊ฐ€ 1๋ฒˆ, ๊ทธ ์˜ค๋ฅธ์ชฝ์€ 2๋ฒˆ, ๊ทธ ์˜ค๋ฅธ์ชฝ์€ 3๋ฒˆ, ๊ฐ€์žฅ ์˜ค๋ฅธ์ชฝ ํ†ฑ๋‹ˆ๋ฐ”ํ€ด๋Š” 4๋ฒˆ์ด๋‹ค. ์ด๋•Œ, ํ†ฑ๋‹ˆ๋ฐ”ํ€ด๋ฅผ ์ด K๋ฒˆ ํšŒ์ „์‹œํ‚ค๋ ค๊ณ  ํ•œ๋‹ค. ํ†ฑ๋‹ˆ๋ฐ”ํ€ด์˜ ํšŒ์ „์€ ํ•œ ์นธ์„ ๊ธฐ์ค€์œผ๋กœ ํ•œ๋‹ค. ํšŒ์ „์€ ์‹œ๊ณ„ ๋ฐฉํ–ฅ๊ณผ ..

[JAVA] BOJ ๋ฐฑ์ค€ 14889 ์Šคํƒ€ํŠธ์™€ ๋งํฌ

https://www.acmicpc.net/problem/14889 14889๋ฒˆ: ์Šคํƒ€ํŠธ์™€ ๋งํฌ ์˜ˆ์ œ 2์˜ ๊ฒฝ์šฐ์— (1, 3, 6), (2, 4, 5)๋กœ ํŒ€์„ ๋‚˜๋ˆ„๋ฉด ๋˜๊ณ , ์˜ˆ์ œ 3์˜ ๊ฒฝ์šฐ์—๋Š” (1, 2, 4, 5), (3, 6, 7, 8)๋กœ ํŒ€์„ ๋‚˜๋ˆ„๋ฉด ๋œ๋‹ค. www.acmicpc.net ๋ฌธ์ œ ์˜ค๋Š˜์€ ์Šคํƒ€ํŠธ๋งํฌ์— ๋‹ค๋‹ˆ๋Š” ์‚ฌ๋žŒ๋“ค์ด ๋ชจ์—ฌ์„œ ์ถ•๊ตฌ๋ฅผ ํ•ด๋ณด๋ ค๊ณ  ํ•œ๋‹ค. ์ถ•๊ตฌ๋Š” ํ‰์ผ ์˜คํ›„์— ํ•˜๊ณ  ์˜๋ฌด ์ฐธ์„๋„ ์•„๋‹ˆ๋‹ค. ์ถ•๊ตฌ๋ฅผ ํ•˜๊ธฐ ์œ„ํ•ด ๋ชจ์ธ ์‚ฌ๋žŒ์€ ์ด N๋ช…์ด๊ณ  ์‹ ๊ธฐํ•˜๊ฒŒ๋„ N์€ ์ง์ˆ˜์ด๋‹ค. ์ด์ œ N/2๋ช…์œผ๋กœ ์ด๋ฃจ์–ด์ง„ ์Šคํƒ€ํŠธ ํŒ€๊ณผ ๋งํฌ ํŒ€์œผ๋กœ ์‚ฌ๋žŒ๋“ค์„ ๋‚˜๋ˆ ์•ผ ํ•œ๋‹ค. BOJ๋ฅผ ์šด์˜ํ•˜๋Š” ํšŒ์‚ฌ ๋‹ต๊ฒŒ ์‚ฌ๋žŒ์—๊ฒŒ ๋ฒˆํ˜ธ๋ฅผ 1๋ถ€ํ„ฐ N๊นŒ์ง€๋กœ ๋ฐฐ์ •ํ–ˆ๊ณ , ์•„๋ž˜์™€ ๊ฐ™์€ ๋Šฅ๋ ฅ์น˜๋ฅผ ์กฐ์‚ฌํ–ˆ๋‹ค. ๋Šฅ๋ ฅ์น˜ Sij๋Š” i๋ฒˆ ์‚ฌ๋žŒ๊ณผ j๋ฒˆ ์‚ฌ๋žŒ์ด ๊ฐ™์€ ํŒ€์— ์†..

[JAVA] BOJ ๋ฐฑ์ค€ 14503 ๋กœ๋ด‡ ์ฒญ์†Œ๊ธฐ

๋ฌธ์ œ ๋กœ๋ด‡ ์ฒญ์†Œ๊ธฐ๊ฐ€ ์ฃผ์–ด์กŒ์„ ๋•Œ, ์ฒญ์†Œํ•˜๋Š” ์˜์—ญ์˜ ๊ฐœ์ˆ˜๋ฅผ ๊ตฌํ•˜๋Š” ํ”„๋กœ๊ทธ๋žจ์„ ์ž‘์„ฑํ•˜์‹œ์˜ค. ๋กœ๋ด‡ ์ฒญ์†Œ๊ธฐ๊ฐ€ ์žˆ๋Š” ์žฅ์†Œ๋Š” N×M ํฌ๊ธฐ์˜ ์ง์‚ฌ๊ฐํ˜•์œผ๋กœ ๋‚˜ํƒ€๋‚ผ ์ˆ˜ ์žˆ์œผ๋ฉฐ, 1×1ํฌ๊ธฐ์˜ ์ •์‚ฌ๊ฐํ˜• ์นธ์œผ๋กœ ๋‚˜๋ˆ„์–ด์ ธ ์žˆ๋‹ค. ๊ฐ๊ฐ์˜ ์นธ์€ ๋ฒฝ ๋˜๋Š” ๋นˆ ์นธ์ด๋‹ค. ์ฒญ์†Œ๊ธฐ๋Š” ๋ฐ”๋ผ๋ณด๋Š” ๋ฐฉํ–ฅ์ด ์žˆ์œผ๋ฉฐ, ์ด ๋ฐฉํ–ฅ์€ ๋™, ์„œ, ๋‚จ, ๋ถ์ค‘ ํ•˜๋‚˜์ด๋‹ค. ์ง€๋„์˜ ๊ฐ ์นธ์€ (r, c)๋กœ ๋‚˜ํƒ€๋‚ผ ์ˆ˜ ์žˆ๊ณ , r์€ ๋ถ์ชฝ์œผ๋กœ๋ถ€ํ„ฐ ๋–จ์–ด์ง„ ์นธ์˜ ๊ฐœ์ˆ˜, c๋Š” ์„œ์ชฝ์œผ๋กœ ๋ถ€ํ„ฐ ๋–จ์–ด์ง„ ์นธ์˜ ๊ฐœ์ˆ˜์ด๋‹ค. → ์ด๋ฅผ ํ†ตํ•ด ๋ฐฐ์—ด์˜ ์ธ๋ฑ์Šค๋ฅผ 0๋ถ€ํ„ฐ ์‹œ์ž‘ํ•ด์•ผ ํ•œ๋‹ค๋Š” ๊ฒƒ์„ ์•Œ์ˆ˜ ์žˆ๋‹ค. ๋กœ๋ด‡ ์ฒญ์†Œ๊ธฐ๋Š” ๋‹ค์Œ๊ณผ ๊ฐ™์ด ์ž‘๋™ํ•œ๋‹ค. ํ˜„์žฌ ์œ„์น˜๋ฅผ ์ฒญ์†Œํ•œ๋‹ค. ํ˜„์žฌ ์œ„์น˜์—์„œ ํ˜„์žฌ ๋ฐฉํ–ฅ์„ ๊ธฐ์ค€์œผ๋กœ ์™ผ์ชฝ๋ฐฉํ–ฅ๋ถ€ํ„ฐ ์ฐจ๋ก€๋Œ€๋กœ ํƒ์ƒ‰์„ ์ง„ํ–‰ํ•œ๋‹ค. ์™ผ์ชฝ ๋ฐฉํ–ฅ์— ์•„์ง ์ฒญ์†Œํ•˜์ง€ ์•Š์€ ๊ณต๊ฐ„์ด ์กด์žฌํ•œ๋‹ค๋ฉด, ๊ทธ ๋ฐฉํ–ฅ..

[JAVA] BOJ ๋ฐฑ์ค€ 14502๋ฒˆ ์—ฐ๊ตฌ์†Œ

https://www.acmicpc.net/problem/14502 ๋ฌธ์ œ ์ธ์ฒด์— ์น˜๋ช…์ ์ธ ๋ฐ”์ด๋Ÿฌ์Šค๋ฅผ ์—ฐ๊ตฌํ•˜๋˜ ์—ฐ๊ตฌ์†Œ์—์„œ ๋ฐ”์ด๋Ÿฌ์Šค๊ฐ€ ์œ ์ถœ๋˜์—ˆ๋‹ค. ๋‹คํ–‰ํžˆ ๋ฐ”์ด๋Ÿฌ์Šค๋Š” ์•„์ง ํผ์ง€์ง€ ์•Š์•˜๊ณ , ๋ฐ”์ด๋Ÿฌ์Šค์˜ ํ™•์‚ฐ์„ ๋ง‰๊ธฐ ์œ„ํ•ด์„œ ์—ฐ๊ตฌ์†Œ์— ๋ฒฝ์„ ์„ธ์šฐ๋ ค๊ณ  ํ•œ๋‹ค. ์—ฐ๊ตฌ์†Œ๋Š” ํฌ๊ธฐ๊ฐ€ N×M์ธ ์ง์‚ฌ๊ฐํ˜•์œผ๋กœ ๋‚˜ํƒ€๋‚ผ ์ˆ˜ ์žˆ์œผ๋ฉฐ, ์ง์‚ฌ๊ฐํ˜•์€ 1×1 ํฌ๊ธฐ์˜ ์ •์‚ฌ๊ฐํ˜•์œผ๋กœ ๋‚˜๋ˆ„์–ด์ ธ ์žˆ๋‹ค. ์—ฐ๊ตฌ์†Œ๋Š” ๋นˆ ์นธ, ๋ฒฝ์œผ๋กœ ์ด๋ฃจ์–ด์ ธ ์žˆ์œผ๋ฉฐ, ๋ฒฝ์€ ์นธ ํ•˜๋‚˜๋ฅผ ๊ฐ€๋“ ์ฐจ์ง€ํ•œ๋‹ค. ์ผ๋ถ€ ์นธ์€ ๋ฐ”์ด๋Ÿฌ์Šค๊ฐ€ ์กด์žฌํ•˜๋ฉฐ, ์ด ๋ฐ”์ด๋Ÿฌ์Šค๋Š” ์ƒํ•˜์ขŒ์šฐ๋กœ ์ธ์ ‘ํ•œ ๋นˆ ์นธ์œผ๋กœ ๋ชจ๋‘ ํผ์ ธ๋‚˜๊ฐˆ ์ˆ˜ ์žˆ๋‹ค. ์ƒˆ๋กœ ์„ธ์šธ ์ˆ˜ ์žˆ๋Š” ๋ฒฝ์˜ ๊ฐœ์ˆ˜๋Š” 3๊ฐœ์ด๋ฉฐ, ๊ผญ 3๊ฐœ๋ฅผ ์„ธ์›Œ์•ผ ํ•œ๋‹ค. ์˜ˆ๋ฅผ ๋“ค์–ด, ์•„๋ž˜์™€ ๊ฐ™์ด ์—ฐ๊ตฌ์†Œ๊ฐ€ ์ƒ๊ธด ๊ฒฝ์šฐ๋ฅผ ์‚ดํŽด๋ณด์ž. 2 0 0 0 1 1 0 0 0 1 0 1 2 0 0 1 ..