์•Œ๊ณ ๋ฆฌ์ฆ˜ ๋ฌธ์ œ 187

[BOJ/Step12] 1427 : ์†ŒํŠธ์ธ์‚ฌ์ด๋“œ (JAVA)

www.acmicpc.net/problem/1427 1427๋ฒˆ: ์†ŒํŠธ์ธ์‚ฌ์ด๋“œ ์ฒซ์งธ ์ค„์— ์ •๋ ฌํ•˜๊ณ ์žํ•˜๋Š” ์ˆ˜ N์ด ์ฃผ์–ด์ง„๋‹ค. N์€ 1,000,000,000๋ณด๋‹ค ์ž‘๊ฑฐ๋‚˜ ๊ฐ™์€ ์ž์—ฐ์ˆ˜์ด๋‹ค. www.acmicpc.net ๋ฌธ์ œ ๋ฐฐ์—ด์„ ์ •๋ ฌํ•˜๋Š” ๊ฒƒ์€ ์‰ฝ๋‹ค. ์ˆ˜๊ฐ€ ์ฃผ์–ด์ง€๋ฉด, ๊ทธ ์ˆ˜์˜ ๊ฐ ์ž๋ฆฌ์ˆ˜๋ฅผ ๋‚ด๋ฆผ์ฐจ์ˆœ์œผ๋กœ ์ •๋ ฌํ•ด๋ณด์ž. ์ž…๋ ฅ ์ฒซ์งธ ์ค„์— ์ •๋ ฌํ•˜๊ณ ์žํ•˜๋Š” ์ˆ˜ N์ด ์ฃผ์–ด์ง„๋‹ค. N์€ 1,000,000,000๋ณด๋‹ค ์ž‘๊ฑฐ๋‚˜ ๊ฐ™์€ ์ž์—ฐ์ˆ˜์ด๋‹ค. ์ถœ๋ ฅ ์ฒซ์งธ ์ค„์— ์ž๋ฆฌ์ˆ˜๋ฅผ ๋‚ด๋ฆผ์ฐจ์ˆœ์œผ๋กœ ์ •๋ ฌํ•œ ์ˆ˜๋ฅผ ์ถœ๋ ฅํ•œ๋‹ค. ์˜ˆ์ œ ์ž…๋ ฅ 1 2143 ์˜ˆ์ œ ์ถœ๋ ฅ 1 4321 ํ’€์ด ๊ทธ๋ƒฅ ์ž…๋ ฅ๋ฐ›์€ ์ˆ˜๋ฅผ ํ•œ์ž๋ฆฌ์”ฉ ๋ถ„๋ฆฌํ•œ ํ›„ ์ •๋ ฌํ•˜์—ฌ ๋‚ด๋ฆผ์ฐจ์ˆœ์œผ๋กœ ์ค„๋ฐ”๊ฟˆ ์—†์ด ์ถœ๋ ฅํ•˜๋ฉด ๋œ๋‹ค 1. ์ฃผ์–ด์ง€๋Š” ์ˆ˜ n์„ String s์— ์ €์žฅํ•œ๋‹ค 2. s์˜ ๊ธธ์ด๋งŒํผ์˜ ๋ฐฐ์—ด์„ ๋งŒ๋“ค๊ณ , s๋ฅผ ํ•œ์ž..

[BOJ/Step12] 2108 : ํ†ต๊ณ„ํ•™ (JAVA)

www.acmicpc.net/problem/2108 2108๋ฒˆ: ํ†ต๊ณ„ํ•™ ์ฒซ์งธ ์ค„์— ์ˆ˜์˜ ๊ฐœ์ˆ˜ N(1 ≤ N ≤ 500,000)์ด ์ฃผ์–ด์ง„๋‹ค. ๊ทธ ๋‹ค์Œ N๊ฐœ์˜ ์ค„์—๋Š” ์ •์ˆ˜๋“ค์ด ์ฃผ์–ด์ง„๋‹ค. ์ž…๋ ฅ๋˜๋Š” ์ •์ˆ˜์˜ ์ ˆ๋Œ“๊ฐ’์€ 4,000์„ ๋„˜์ง€ ์•Š๋Š”๋‹ค. www.acmicpc.net ๋ฌธ์ œ ์ˆ˜๋ฅผ ์ฒ˜๋ฆฌํ•˜๋Š” ๊ฒƒ์€ ํ†ต๊ณ„ํ•™์—์„œ ์ƒ๋‹นํžˆ ์ค‘์š”ํ•œ ์ผ์ด๋‹ค. ํ†ต๊ณ„ํ•™์—์„œ N๊ฐœ์˜ ์ˆ˜๋ฅผ ๋Œ€ํ‘œํ•˜๋Š” ๊ธฐ๋ณธ ํ†ต๊ณ„๊ฐ’์—๋Š” ๋‹ค์Œ๊ณผ ๊ฐ™์€ ๊ฒƒ๋“ค์ด ์žˆ๋‹ค. ๋‹จ, N์€ ํ™€์ˆ˜๋ผ๊ณ  ๊ฐ€์ •ํ•˜์ž. - ์‚ฐ์ˆ ํ‰๊ท  : N๊ฐœ์˜ ์ˆ˜๋“ค์˜ ํ•ฉ์„ N์œผ๋กœ ๋‚˜๋ˆˆ ๊ฐ’ - ์ค‘์•™๊ฐ’ : N๊ฐœ์˜ ์ˆ˜๋“ค์„ ์ฆ๊ฐ€ํ•˜๋Š” ์ˆœ์„œ๋กœ ๋‚˜์—ดํ–ˆ์„ ๊ฒฝ์šฐ ๊ทธ ์ค‘์•™์— ์œ„์น˜ํ•˜๋Š” ๊ฐ’ - ์ตœ๋นˆ๊ฐ’ : N๊ฐœ์˜ ์ˆ˜๋“ค ์ค‘ ๊ฐ€์žฅ ๋งŽ์ด ๋‚˜ํƒ€๋‚˜๋Š” ๊ฐ’ - ๋ฒ”์œ„ : N๊ฐœ์˜ ์ˆ˜๋“ค ์ค‘ ์ตœ๋Œ“๊ฐ’๊ณผ ์ตœ์†Ÿ๊ฐ’์˜ ์ฐจ์ด N๊ฐœ์˜ ์ˆ˜๊ฐ€ ์ฃผ์–ด์กŒ์„ ๋•Œ, ๋„ค ๊ฐ€์ง€ ๊ธฐ๋ณธ ํ†ต๊ณ„..

[BOJ/Step12] 10989 : ์ˆ˜ ์ •๋ ฌํ•˜๊ธฐ 3 (JAVA)

www.acmicpc.net/problem/10989 10989๋ฒˆ: ์ˆ˜ ์ •๋ ฌํ•˜๊ธฐ 3 ์ฒซ์งธ ์ค„์— ์ˆ˜์˜ ๊ฐœ์ˆ˜ N(1 ≤ N ≤ 10,000,000)์ด ์ฃผ์–ด์ง„๋‹ค. ๋‘˜์งธ ์ค„๋ถ€ํ„ฐ N๊ฐœ์˜ ์ค„์—๋Š” ์ˆซ์ž๊ฐ€ ์ฃผ์–ด์ง„๋‹ค. ์ด ์ˆ˜๋Š” 10,000๋ณด๋‹ค ์ž‘๊ฑฐ๋‚˜ ๊ฐ™์€ ์ž์—ฐ์ˆ˜์ด๋‹ค. www.acmicpc.net ๋ฌธ์ œ N๊ฐœ์˜ ์ˆ˜๊ฐ€ ์ฃผ์–ด์กŒ์„ ๋•Œ, ์ด๋ฅผ ์˜ค๋ฆ„์ฐจ์ˆœ์œผ๋กœ ์ •๋ ฌํ•˜๋Š” ํ”„๋กœ๊ทธ๋žจ์„ ์ž‘์„ฑํ•˜์‹œ์˜ค. ์ž…๋ ฅ ์ฒซ์งธ ์ค„์— ์ˆ˜์˜ ๊ฐœ์ˆ˜ N(1 ≤ N ≤ 10,000,000)์ด ์ฃผ์–ด์ง„๋‹ค. ๋‘˜์งธ ์ค„๋ถ€ํ„ฐ N๊ฐœ์˜ ์ค„์—๋Š” ์ˆซ์ž๊ฐ€ ์ฃผ์–ด์ง„๋‹ค. ์ด ์ˆ˜๋Š” 10,000๋ณด๋‹ค ์ž‘๊ฑฐ๋‚˜ ๊ฐ™์€ ์ž์—ฐ์ˆ˜์ด๋‹ค. ์ถœ๋ ฅ ์ฒซ์งธ ์ค„๋ถ€ํ„ฐ N๊ฐœ์˜ ์ค„์— ์˜ค๋ฆ„์ฐจ์ˆœ์œผ๋กœ ์ •๋ ฌํ•œ ๊ฒฐ๊ณผ๋ฅผ ํ•œ ์ค„์— ํ•˜๋‚˜์”ฉ ์ถœ๋ ฅํ•œ๋‹ค. ์˜ˆ์ œ ์ž…๋ ฅ 1 10 5 2 3 1 4 2 3 5 1 7 ์˜ˆ์ œ ์ถœ๋ ฅ 1 1 1 2 2 3 3 ..

[BOJ/Step12] 2751 : ์ˆ˜ ์ •๋ ฌํ•˜๊ธฐ 2 (JAVA)

www.acmicpc.net/problem/2751 2751๋ฒˆ: ์ˆ˜ ์ •๋ ฌํ•˜๊ธฐ 2 ์ฒซ์งธ ์ค„์— ์ˆ˜์˜ ๊ฐœ์ˆ˜ N(1 ≤ N ≤ 1,000,000)์ด ์ฃผ์–ด์ง„๋‹ค. ๋‘˜์งธ ์ค„๋ถ€ํ„ฐ N๊ฐœ์˜ ์ค„์—๋Š” ์ˆซ์ž๊ฐ€ ์ฃผ์–ด์ง„๋‹ค. ์ด ์ˆ˜๋Š” ์ ˆ๋Œ“๊ฐ’์ด 1,000,000๋ณด๋‹ค ์ž‘๊ฑฐ๋‚˜ ๊ฐ™์€ ์ •์ˆ˜์ด๋‹ค. ์ˆ˜๋Š” ์ค‘๋ณต๋˜์ง€ ์•Š๋Š”๋‹ค. www.acmicpc.net ๋ฌธ์ œ N๊ฐœ์˜ ์ˆ˜๊ฐ€ ์ฃผ์–ด์กŒ์„ ๋•Œ, ์ด๋ฅผ ์˜ค๋ฆ„์ฐจ์ˆœ์œผ๋กœ ์ •๋ ฌํ•˜๋Š” ํ”„๋กœ๊ทธ๋žจ์„ ์ž‘์„ฑํ•˜์‹œ์˜ค. ์ž…๋ ฅ ์ฒซ์งธ ์ค„์— ์ˆ˜์˜ ๊ฐœ์ˆ˜ N(1 ≤ N ≤ 1,000,000)์ด ์ฃผ์–ด์ง„๋‹ค. ๋‘˜์งธ ์ค„๋ถ€ํ„ฐ N๊ฐœ์˜ ์ค„์—๋Š” ์ˆซ์ž๊ฐ€ ์ฃผ์–ด์ง„๋‹ค. ์ด ์ˆ˜๋Š” ์ ˆ๋Œ“๊ฐ’์ด 1,000,000๋ณด๋‹ค ์ž‘๊ฑฐ๋‚˜ ๊ฐ™์€ ์ •์ˆ˜์ด๋‹ค. ์ˆ˜๋Š” ์ค‘๋ณต๋˜์ง€ ์•Š๋Š”๋‹ค. ์ถœ๋ ฅ ์ฒซ์งธ ์ค„๋ถ€ํ„ฐ N๊ฐœ์˜ ์ค„์— ์˜ค๋ฆ„์ฐจ์ˆœ์œผ๋กœ ์ •๋ ฌํ•œ ๊ฒฐ๊ณผ๋ฅผ ํ•œ ์ค„์— ํ•˜๋‚˜์”ฉ ์ถœ๋ ฅํ•œ๋‹ค. ์˜ˆ์ œ ์ž…๋ ฅ 1 5 5 4 3..

[BOJ/Step12] 2750 : ์ˆ˜ ์ •๋ ฌํ•˜๊ธฐ (JAVA)

www.acmicpc.net/problem/2750 2750๋ฒˆ: ์ˆ˜ ์ •๋ ฌํ•˜๊ธฐ ์ฒซ์งธ ์ค„์— ์ˆ˜์˜ ๊ฐœ์ˆ˜ N(1 ≤ N ≤ 1,000)์ด ์ฃผ์–ด์ง„๋‹ค. ๋‘˜์งธ ์ค„๋ถ€ํ„ฐ N๊ฐœ์˜ ์ค„์—๋Š” ์ˆซ์ž๊ฐ€ ์ฃผ์–ด์ง„๋‹ค. ์ด ์ˆ˜๋Š” ์ ˆ๋Œ“๊ฐ’์ด 1,000๋ณด๋‹ค ์ž‘๊ฑฐ๋‚˜ ๊ฐ™์€ ์ •์ˆ˜์ด๋‹ค. ์ˆ˜๋Š” ์ค‘๋ณต๋˜์ง€ ์•Š๋Š”๋‹ค. www.acmicpc.net ๋ฌธ์ œ N๊ฐœ์˜ ์ˆ˜๊ฐ€ ์ฃผ์–ด์กŒ์„ ๋•Œ, ์ด๋ฅผ ์˜ค๋ฆ„์ฐจ์ˆœ์œผ๋กœ ์ •๋ ฌํ•˜๋Š” ํ”„๋กœ๊ทธ๋žจ์„ ์ž‘์„ฑํ•˜์‹œ์˜ค. ์ž…๋ ฅ ์ฒซ์งธ ์ค„์— ์ˆ˜์˜ ๊ฐœ์ˆ˜ N(1 ≤ N ≤ 1,000)์ด ์ฃผ์–ด์ง„๋‹ค. ๋‘˜์งธ ์ค„๋ถ€ํ„ฐ N๊ฐœ์˜ ์ค„์—๋Š” ์ˆซ์ž๊ฐ€ ์ฃผ์–ด์ง„๋‹ค. ์ด ์ˆ˜๋Š” ์ ˆ๋Œ“๊ฐ’์ด 1,000๋ณด๋‹ค ์ž‘๊ฑฐ๋‚˜ ๊ฐ™์€ ์ •์ˆ˜์ด๋‹ค. ์ˆ˜๋Š” ์ค‘๋ณต๋˜์ง€ ์•Š๋Š”๋‹ค. ์ถœ๋ ฅ ์ฒซ์งธ ์ค„๋ถ€ํ„ฐ N๊ฐœ์˜ ์ค„์— ์˜ค๋ฆ„์ฐจ์ˆœ์œผ๋กœ ์ •๋ ฌํ•œ ๊ฒฐ๊ณผ๋ฅผ ํ•œ ์ค„์— ํ•˜๋‚˜์”ฉ ์ถœ๋ ฅํ•œ๋‹ค. ์˜ˆ์ œ ์ž…๋ ฅ 5 5 2 3 4 1 ์˜ˆ์ œ ์ถœ๋ ฅ 1 2 3 4 5..

[BOJ/Step11] 1436 : ์˜ํ™”๊ฐ๋… ์ˆŒ (JAVA)

www.acmicpc.net/problem/1436 1436๋ฒˆ: ์˜ํ™”๊ฐ๋… ์ˆŒ 666์€ ์ข…๋ง์„ ๋‚˜ํƒ€๋‚ด๋Š” ์ˆซ์ž๋ผ๊ณ  ํ•œ๋‹ค. ๋”ฐ๋ผ์„œ, ๋งŽ์€ ๋ธ”๋ก๋ฒ„์Šคํ„ฐ ์˜ํ™”์—์„œ๋Š” 666์ด ๋“ค์–ด๊ฐ„ ์ œ๋ชฉ์„ ๋งŽ์ด ์‚ฌ์šฉํ•œ๋‹ค. ์˜ํ™”๊ฐ๋… ์ˆŒ์€ ์„ธ์ƒ์˜ ์ข…๋ง ์ด๋ผ๋Š” ์‹œ๋ฆฌ์ฆˆ ์˜ํ™”์˜ ๊ฐ๋…์ด๋‹ค. ์กฐ์ง€ ๋ฃจ์นด์Šค๋Š” ์Šคํƒ€ www.acmicpc.net ๋ฌธ์ œ 666์€ ์ข…๋ง์„ ๋‚˜ํƒ€๋‚ด๋Š” ์ˆซ์ž๋ผ๊ณ  ํ•œ๋‹ค. ๋”ฐ๋ผ์„œ, ๋งŽ์€ ๋ธ”๋ก๋ฒ„์Šคํ„ฐ ์˜ํ™”์—์„œ๋Š” 666์ด ๋“ค์–ด๊ฐ„ ์ œ๋ชฉ์„ ๋งŽ์ด ์‚ฌ์šฉํ•œ๋‹ค. ์˜ํ™”๊ฐ๋… ์ˆŒ์€ ์„ธ์ƒ์˜ ์ข…๋ง ์ด๋ผ๋Š” ์‹œ๋ฆฌ์ฆˆ ์˜ํ™”์˜ ๊ฐ๋…์ด๋‹ค. ์กฐ์ง€ ๋ฃจ์นด์Šค๋Š” ์Šคํƒ€์›Œ์ฆˆ๋ฅผ ๋งŒ๋“ค ๋•Œ, ์Šคํƒ€์›Œ์ฆˆ 1, ์Šคํƒ€์›Œ์ฆˆ 2, ์Šคํƒ€์›Œ์ฆˆ 3, ์Šคํƒ€์›Œ์ฆˆ 4, ์Šคํƒ€์›Œ์ฆˆ 5, ์Šคํƒ€์›Œ์ฆˆ 6๊ณผ ๊ฐ™์ด ์ด๋ฆ„์„ ์ง€์—ˆ๊ณ , ํ”ผํ„ฐ ์žญ์Šจ์€ ๋ฐ˜์ง€์˜ ์ œ์™•์„ ๋งŒ๋“ค ๋•Œ, ๋ฐ˜์ง€์˜ ์ œ์™• 1, ๋ฐ˜์ง€์˜ ์ œ์™• 2, ๋ฐ˜์ง€์˜ ์ œ์™• 3..

[BOJ/Step11] 1018 : ์ฒด์ŠคํŒ ๋‹ค์‹œ ์น ํ•˜๊ธฐ (JAVA)

www.acmicpc.net/problem/1018 1018๋ฒˆ: ์ฒด์ŠคํŒ ๋‹ค์‹œ ์น ํ•˜๊ธฐ ์ฒซ์งธ ์ค„์— N๊ณผ M์ด ์ฃผ์–ด์ง„๋‹ค. N๊ณผ M์€ 8๋ณด๋‹ค ํฌ๊ฑฐ๋‚˜ ๊ฐ™๊ณ , 50๋ณด๋‹ค ์ž‘๊ฑฐ๋‚˜ ๊ฐ™์€ ์ž์—ฐ์ˆ˜์ด๋‹ค. ๋‘˜์งธ ์ค„๋ถ€ํ„ฐ N๊ฐœ์˜ ์ค„์—๋Š” ๋ณด๋“œ์˜ ๊ฐ ํ–‰์˜ ์ƒํƒœ๊ฐ€ ์ฃผ์–ด์ง„๋‹ค. B๋Š” ๊ฒ€์€์ƒ‰์ด๋ฉฐ, W๋Š” ํฐ์ƒ‰์ด๋‹ค. www.acmicpc.net ๋ฌธ์ œ ์ง€๋ฏผ์ด๋Š” ์ž์‹ ์˜ ์ €ํƒ์—์„œ MN๊ฐœ์˜ ๋‹จ์œ„ ์ •์‚ฌ๊ฐํ˜•์œผ๋กœ ๋‚˜๋ˆ„์–ด์ ธ ์žˆ๋Š” M*N ํฌ๊ธฐ์˜ ๋ณด๋“œ๋ฅผ ์ฐพ์•˜๋‹ค. ์–ด๋–ค ์ •์‚ฌ๊ฐํ˜•์€ ๊ฒ€์€์ƒ‰์œผ๋กœ ์น ํ•ด์ ธ ์žˆ๊ณ , ๋‚˜๋จธ์ง€๋Š” ํฐ์ƒ‰์œผ๋กœ ์น ํ•ด์ ธ ์žˆ๋‹ค. ์ง€๋ฏผ์ด๋Š” ์ด ๋ณด๋“œ๋ฅผ ์ž˜๋ผ์„œ 8*8 ํฌ๊ธฐ์˜ ์ฒด์ŠคํŒ์œผ๋กœ ๋งŒ๋“ค๋ ค๊ณ  ํ•œ๋‹ค. ์ฒด์ŠคํŒ์€ ๊ฒ€์€์ƒ‰๊ณผ ํฐ์ƒ‰์ด ๋ฒˆ๊ฐˆ์•„์„œ ์น ํ•ด์ ธ ์žˆ์–ด์•ผ ํ•œ๋‹ค. ๊ตฌ์ฒด์ ์œผ๋กœ, ๊ฐ ์นธ์ด ๊ฒ€์€์ƒ‰๊ณผ ํฐ์ƒ‰ ์ค‘ ํ•˜๋‚˜๋กœ ์ƒ‰์น ๋˜์–ด ์žˆ๊ณ , ๋ณ€์„ ๊ณต์œ ํ•˜๋Š” ๋‘ ๊ฐœ์˜ ์‚ฌ๊ฐํ˜•์€ ๋‹ค๋ฅธ ์ƒ‰์œผ๋กœ ..

[BOJ/Step11] 7568 : ๋ฉ์น˜ (JAVA)

www.acmicpc.net/problem/7568 7568๋ฒˆ: ๋ฉ์น˜ ์šฐ๋ฆฌ๋Š” ์‚ฌ๋žŒ์˜ ๋ฉ์น˜๋ฅผ ํ‚ค์™€ ๋ชธ๋ฌด๊ฒŒ, ์ด ๋‘ ๊ฐœ์˜ ๊ฐ’์œผ๋กœ ํ‘œํ˜„ํ•˜์—ฌ ๊ทธ ๋“ฑ์ˆ˜๋ฅผ ๋งค๊ฒจ๋ณด๋ ค๊ณ  ํ•œ๋‹ค. ์–ด๋–ค ์‚ฌ๋žŒ์˜ ๋ชธ๋ฌด๊ฒŒ๊ฐ€ x kg์ด๊ณ  ํ‚ค๊ฐ€ y cm๋ผ๋ฉด ์ด ์‚ฌ๋žŒ์˜ ๋ฉ์น˜๋Š” (x, y)๋กœ ํ‘œ์‹œ๋œ๋‹ค. ๋‘ ์‚ฌ๋žŒ A ์™€ B์˜ ๋ฉ www.acmicpc.net ๋ฌธ์ œ ์šฐ๋ฆฌ๋Š” ์‚ฌ๋žŒ์˜ ๋ฉ์น˜๋ฅผ ํ‚ค์™€ ๋ชธ๋ฌด๊ฒŒ, ์ด ๋‘ ๊ฐœ์˜ ๊ฐ’์œผ๋กœ ํ‘œํ˜„ํ•˜์—ฌ ๊ทธ ๋“ฑ์ˆ˜๋ฅผ ๋งค๊ฒจ๋ณด๋ ค๊ณ  ํ•œ๋‹ค. ์–ด๋–ค ์‚ฌ๋žŒ์˜ ๋ชธ๋ฌด๊ฒŒ๊ฐ€ x kg์ด๊ณ  ํ‚ค๊ฐ€ y cm๋ผ๋ฉด ์ด ์‚ฌ๋žŒ์˜ ๋ฉ์น˜๋Š” (x, y)๋กœ ํ‘œ์‹œ๋œ๋‹ค. ๋‘ ์‚ฌ๋žŒ A ์™€ B์˜ ๋ฉ์น˜๊ฐ€ ๊ฐ๊ฐ (x, y), (p, q)๋ผ๊ณ  ํ•  ๋•Œ x > p ๊ทธ๋ฆฌ๊ณ  y > q ์ด๋ผ๋ฉด ์šฐ๋ฆฌ๋Š” A์˜ ๋ฉ์น˜๊ฐ€ B์˜ ๋ฉ์น˜๋ณด๋‹ค "๋” ํฌ๋‹ค"๊ณ  ๋งํ•œ๋‹ค. ์˜ˆ๋ฅผ ๋“ค์–ด ์–ด๋–ค A, B ๋‘ ์‚ฌ๋žŒ์˜ ๋ฉ์น˜๊ฐ€ ..

[BOJ/Step11] 2231 : ๋ถ„ํ•ดํ•ฉ (JAVA)

www.acmicpc.net/problem/2231 2231๋ฒˆ: ๋ถ„ํ•ดํ•ฉ ์–ด๋–ค ์ž์—ฐ์ˆ˜ N์ด ์žˆ์„ ๋•Œ, ๊ทธ ์ž์—ฐ์ˆ˜ N์˜ ๋ถ„ํ•ดํ•ฉ์€ N๊ณผ N์„ ์ด๋ฃจ๋Š” ๊ฐ ์ž๋ฆฌ์ˆ˜์˜ ํ•ฉ์„ ์˜๋ฏธํ•œ๋‹ค. ์–ด๋–ค ์ž์—ฐ์ˆ˜ M์˜ ๋ถ„ํ•ดํ•ฉ์ด N์ธ ๊ฒฝ์šฐ, M์„ N์˜ ์ƒ์„ฑ์ž๋ผ ํ•œ๋‹ค. ์˜ˆ๋ฅผ ๋“ค์–ด, 245์˜ ๋ถ„ํ•ดํ•ฉ์€ 256(=245+2+4+5)์ด www.acmicpc.net ๋ฌธ์ œ ์–ด๋–ค ์ž์—ฐ์ˆ˜ N์ด ์žˆ์„ ๋•Œ, ๊ทธ ์ž์—ฐ์ˆ˜ N์˜ ๋ถ„ํ•ดํ•ฉ์€ N๊ณผ N์„ ์ด๋ฃจ๋Š” ๊ฐ ์ž๋ฆฌ์ˆ˜์˜ ํ•ฉ์„ ์˜๋ฏธํ•œ๋‹ค. ์–ด๋–ค ์ž์—ฐ์ˆ˜ M์˜ ๋ถ„ํ•ดํ•ฉ์ด N์ธ ๊ฒฝ์šฐ, M์„ N์˜ ์ƒ์„ฑ์ž๋ผ ํ•œ๋‹ค. ์˜ˆ๋ฅผ ๋“ค์–ด, 245์˜ ๋ถ„ํ•ดํ•ฉ์€ 256(=245+2+4+5)์ด ๋œ๋‹ค. ๋”ฐ๋ผ์„œ 245๋Š” 256์˜ ์ƒ์„ฑ์ž๊ฐ€ ๋œ๋‹ค. ๋ฌผ๋ก , ์–ด๋–ค ์ž์—ฐ์ˆ˜์˜ ๊ฒฝ์šฐ์—๋Š” ์ƒ์„ฑ์ž๊ฐ€ ์—†์„ ์ˆ˜๋„ ์žˆ๋‹ค. ๋ฐ˜๋Œ€๋กœ, ์ƒ์„ฑ์ž๊ฐ€ ์—ฌ๋Ÿฌ ๊ฐœ์ธ ์ž์—ฐ์ˆ˜๋„ ์žˆ์„ ์ˆ˜ ..

[BOJ/Step11] 2798 : ๋ธ”๋ž™์žญ (JAVA)

www.acmicpc.net/problem/2798 2798๋ฒˆ: ๋ธ”๋ž™์žญ ์ฒซ์งธ ์ค„์— ์นด๋“œ์˜ ๊ฐœ์ˆ˜ N(3 ≤ N ≤ 100)๊ณผ M(10 ≤ M ≤ 300,000)์ด ์ฃผ์–ด์ง„๋‹ค. ๋‘˜์งธ ์ค„์—๋Š” ์นด๋“œ์— ์“ฐ์—ฌ ์žˆ๋Š” ์ˆ˜๊ฐ€ ์ฃผ์–ด์ง€๋ฉฐ, ์ด ๊ฐ’์€ 100,000์„ ๋„˜์ง€ ์•Š๋Š” ์–‘์˜ ์ •์ˆ˜์ด๋‹ค. ํ•ฉ์ด M์„ ๋„˜์ง€ ์•Š๋Š” ์นด๋“œ 3์žฅ www.acmicpc.net ๋ฌธ์ œ ์นด์ง€๋…ธ์—์„œ ์ œ์ผ ์ธ๊ธฐ ์žˆ๋Š” ๊ฒŒ์ž„ ๋ธ”๋ž™์žญ์˜ ๊ทœ์น™์€ ์ƒ๋‹นํžˆ ์‰ฝ๋‹ค. ์นด๋“œ์˜ ํ•ฉ์ด 21์„ ๋„˜์ง€ ์•Š๋Š” ํ•œ๋„ ๋‚ด์—์„œ, ์นด๋“œ์˜ ํ•ฉ์„ ์ตœ๋Œ€ํ•œ ํฌ๊ฒŒ ๋งŒ๋“œ๋Š” ๊ฒŒ์ž„์ด๋‹ค. ๋ธ”๋ž™์žญ์€ ์นด์ง€๋…ธ๋งˆ๋‹ค ๋‹ค์–‘ํ•œ ๊ทœ์ •์ด ์žˆ๋‹ค. ํ•œ๊ตญ ์ตœ๊ณ ์˜ ๋ธ”๋ž™์žญ ๊ณ ์ˆ˜ ๊น€์ •์ธ์€ ์ƒˆ๋กœ์šด ๋ธ”๋ž™์žญ ๊ทœ์น™์„ ๋งŒ๋“ค์–ด ์ƒ๊ทผ, ์ฐฝ์˜์ด์™€ ๊ฒŒ์ž„ํ•˜๋ ค๊ณ  ํ•œ๋‹ค. ๊น€์ •์ธ ๋ฒ„์ „์˜ ๋ธ”๋ž™์žญ์—์„œ ๊ฐ ์นด๋“œ์—๋Š” ์–‘์˜ ์ •์ˆ˜๊ฐ€ ์“ฐ์—ฌ ์žˆ๋‹ค. ๊ทธ ๋‹ค์Œ, ๋”œ๋Ÿฌ๋Š” N์žฅ์˜ ..