2798 2

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

www.acmicpc.net/problem/2798 2798๋ฒˆ: ๋ธ”๋ž™์žญ ์ฒซ์งธ ์ค„์— ์นด๋“œ์˜ ๊ฐœ์ˆ˜ N(3 ≤ N ≤ 100)๊ณผ M(10 ≤ M ≤ 300,000)์ด ์ฃผ์–ด์ง„๋‹ค. ๋‘˜์งธ ์ค„์—๋Š” ์นด๋“œ์— ์“ฐ์—ฌ ์žˆ๋Š” ์ˆ˜๊ฐ€ ์ฃผ์–ด์ง€๋ฉฐ, ์ด ๊ฐ’์€ 100,000์„ ๋„˜์ง€ ์•Š๋Š” ์–‘์˜ ์ •์ˆ˜์ด๋‹ค. ํ•ฉ์ด M์„ ๋„˜์ง€ ์•Š๋Š” ์นด๋“œ 3์žฅ www.acmicpc.net N๊ฐœ์˜ ์นด๋“œ ์ค‘ M์„ ๋„˜์ง€ ์•Š๋Š” ์„ธ ๊ฐœ์˜ ํ•ฉ์˜ ์ตœ๋Œ€๊ฐ’์„ ๊ตฌํ•˜๋Š” ๋ฌธ์ œ 1. i๋Š” 0๋ถ€ํ„ฐ n-2๊นŒ์ง€, j๋Š” i+1๋ถ€ํ„ฐ n-1๊นŒ์ง€, l์€ j+1๋ถ€ํ„ฐ n๊นŒ์ง€ ์ˆœ์„œ๋Œ€๋กœ ๊ณจ๋ผ ๋”ํ•œ๋‹ค ( i๋ฅผ ๊ณ ๋ฅด๋ฉด j๋Š” i ์ด์ „์˜ ์นด๋“œ๋ฅผ ๊ณ ๋ฅผ ํ•„์š”๊ฐ€ ์—†๊ณ  i๊ฐ€ n-2์ผ๋•Œ n-1๊ณผ n์€ ๊ฐ๊ฐ j์™€ l์ด ๋˜๊ธฐ ๋•Œ๋ฌธ์— n-2๊นŒ์ง€๋งŒ ๊ณ ๋ฅด๋ฉด ๋œ๋‹ค ) 2. i + j + l ์ด total๋ณด๋‹ค ํฌ๊ณ  m๊ณผ ๊ฐ™๊ฑฐ๋‚˜ ์ž‘์„๋•Œ..

[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์žฅ์˜ ..