๋ณธ๋ฌธ ๋ฐ”๋กœ๊ฐ€๊ธฐ

SNS1

[BOJ] 2533 : ์‚ฌํšŒ๋ง ์„œ๋น„์Šค(SNS) ๋ฌธ์ œ ๋งํฌ 2533๋ฒˆ: ์‚ฌํšŒ๋ง ์„œ๋น„์Šค(SNS) (acmicpc.net) 2533๋ฒˆ: ์‚ฌํšŒ๋ง ์„œ๋น„์Šค(SNS) ์ฒซ ๋ฒˆ์งธ ์ค„์—๋Š” ์นœ๊ตฌ ๊ด€๊ณ„ ํŠธ๋ฆฌ์˜ ์ •์  ๊ฐœ์ˆ˜ N์ด ์ฃผ์–ด์ง„๋‹ค. ๋‹จ, 2 ≤ N ≤ 1,000,000์ด๋ฉฐ, ๊ฐ ์ •์ ์€ 1๋ถ€ํ„ฐ N๊นŒ์ง€ ์ผ๋ จ๋ฒˆํ˜ธ๋กœ ํ‘œํ˜„๋œ๋‹ค. ๋‘ ๋ฒˆ์งธ ์ค„๋ถ€ํ„ฐ N-1๊ฐœ์˜ ์ค„์—๋Š” ๊ฐ ์ค„๋งˆ๋‹ค ์นœ๊ตฌ ๊ด€๊ณ„ ํŠธ๋ฆฌ์˜ ์— www.acmicpc.net ํŠธ๋ฆฌ๋กœ ์ด๋ฃจ์–ด์ง„ ์‚ฌํšŒ๊ด€๊ณ„๋ง์—์„œ ๋ชจ๋‘๊ฐ€ ์ƒˆ๋กœ์šด ๊ฒƒ์„ ๋ฐ›์•„๋“ค์ด๊ธฐ ์œ„ํ•ด ํ•„์š”ํ•œ ์ตœ์†Œ ์–ผ๋ฆฌ์–ด๋‹ตํ„ฐ ์ˆ˜๋ฅผ ๊ตฌํ•˜๋Š” ๋ฌธ์ œ. ํ’€์ด ๊ธฐ์กด์˜ DP๋ฌธ์ œ์™€๋Š” ๋‹ค๋ฅด๊ฒŒ ํŠธ๋ฆฌ์™€ DP๊ฐ€ ํ•ฉ์ณ์ง„ ๋ฌธ์ œ. ํ•˜๋‚˜์˜ ์ •์ ์— ๋Œ€ํ•ด์„œ ์šฐ๋ฆฌ๋Š” 2๊ฐ€์ง€ ๊ฒฝ์šฐ๋กœ ๋‚˜๋ˆ ์„œ ๋ณผ ์ˆ˜ ์žˆ๋‹ค. ํ•ด๋‹น ์ •์ ์ด ์–ผ๋ฆฌ์–ด๋‹ตํ„ฐ์ด๊ฑฐ๋‚˜ ์–ผ๋ฆฌ์–ด๋‹ตํ„ฐ๊ฐ€ ์•„๋‹ˆ๊ฑฐ๋‚˜. 0์„ ์–ผ๋ฆฌ์–ด๋‹ตํ„ฐ์ธ ๊ฒฝ์šฐ, 1์„ ์–ผ๋ฆฌ์–ด๋‹ตํ„ฐ๊ฐ€ ์•„๋‹Œ๊ฒฝ์šฐ๋กœ ์ƒ๊ฐํ•˜๊ณ  DP๋ฐฐ์—ด์„ .. 2022. 4. 5.

ํ‹ฐ์Šคํ† ๋ฆฌํˆด๋ฐ”