๊ด€๋ฆฌ ๋ฉ”๋‰ด

๋ชฉ๋ก์‹œ๊ฐ„์ดˆ๊ณผ (1)

CS Student’s SAP&Tech Journey๐Ÿ’ซ

[๋ฐฑ์ค€] 2108๋ฒˆ: ํ†ต๊ณ„ํ•™

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