1929 2

[BOJ/Step9] 1929 : ์†Œ์ˆ˜ ๊ตฌํ•˜๊ธฐ (Python)

www.acmicpc.net/problem/1929 1929๋ฒˆ: ์†Œ์ˆ˜ ๊ตฌํ•˜๊ธฐ ์ฒซ์งธ ์ค„์— ์ž์—ฐ์ˆ˜ M๊ณผ N์ด ๋นˆ ์นธ์„ ์‚ฌ์ด์— ๋‘๊ณ  ์ฃผ์–ด์ง„๋‹ค. (1 ≤ M ≤ N ≤ 1,000,000) M์ด์ƒ N์ดํ•˜์˜ ์†Œ์ˆ˜๊ฐ€ ํ•˜๋‚˜ ์ด์ƒ ์žˆ๋Š” ์ž…๋ ฅ๋งŒ ์ฃผ์–ด์ง„๋‹ค. www.acmicpc.net ๋ฌธ์ œ M์ด์ƒ N์ดํ•˜์˜ ์†Œ์ˆ˜๋ฅผ ๋ชจ๋‘ ์ถœ๋ ฅํ•˜๋Š” ํ”„๋กœ๊ทธ๋žจ์„ ์ž‘์„ฑํ•˜์‹œ์˜ค. ์ž…๋ ฅ ์ฒซ์งธ ์ค„์— ์ž์—ฐ์ˆ˜ M๊ณผ N์ด ๋นˆ ์นธ์„ ์‚ฌ์ด์— ๋‘๊ณ  ์ฃผ์–ด์ง„๋‹ค. (1 ≤ M ≤ N ≤ 1,000,000) M์ด์ƒ N์ดํ•˜์˜ ์†Œ์ˆ˜๊ฐ€ ํ•˜๋‚˜ ์ด์ƒ ์žˆ๋Š” ์ž…๋ ฅ๋งŒ ์ฃผ์–ด์ง„๋‹ค. ์ถœ๋ ฅ ํ•œ ์ค„์— ํ•˜๋‚˜์”ฉ, ์ฆ๊ฐ€ํ•˜๋Š” ์ˆœ์„œ๋Œ€๋กœ ์†Œ์ˆ˜๋ฅผ ์ถœ๋ ฅํ•œ๋‹ค. ์˜ˆ์ œ ์ž…๋ ฅ 1 3 16 ์˜ˆ์ œ ์ถœ๋ ฅ 1 3 5 7 11 13 ํ’€์ด (1) m๊ณผ n ์‚ฌ์ด ์ˆซ์ž๋ฅผ ๊ฐ๊ฐ ์†Œ์ˆ˜ ํŒ๋ณ„ 1. ์†Œ์ˆ˜๋ฉด True๋ฅผ, ์•„๋‹ˆ๋ฉด False๋ฅผ ..

[BOJ/Step9] 1929 : ์†Œ์ˆ˜ ๊ตฌํ•˜๊ธฐ (JAVA)

www.acmicpc.net/problem/1929 1929๋ฒˆ: ์†Œ์ˆ˜ ๊ตฌํ•˜๊ธฐ ์ฒซ์งธ ์ค„์— ์ž์—ฐ์ˆ˜ M๊ณผ N์ด ๋นˆ ์นธ์„ ์‚ฌ์ด์— ๋‘๊ณ  ์ฃผ์–ด์ง„๋‹ค. (1 ≤ M ≤ N ≤ 1,000,000) M์ด์ƒ N์ดํ•˜์˜ ์†Œ์ˆ˜๊ฐ€ ํ•˜๋‚˜ ์ด์ƒ ์žˆ๋Š” ์ž…๋ ฅ๋งŒ ์ฃผ์–ด์ง„๋‹ค. www.acmicpc.net ๋ฌธ์ œ M์ด์ƒ N์ดํ•˜์˜ ์†Œ์ˆ˜๋ฅผ ๋ชจ๋‘ ์ถœ๋ ฅํ•˜๋Š” ํ”„๋กœ๊ทธ๋žจ์„ ์ž‘์„ฑํ•˜์‹œ์˜ค. ์ž…๋ ฅ ์ฒซ์งธ ์ค„์— ์ž์—ฐ์ˆ˜ M๊ณผ N์ด ๋นˆ ์นธ์„ ์‚ฌ์ด์— ๋‘๊ณ  ์ฃผ์–ด์ง„๋‹ค. (1 ≤ M ≤ N ≤ 1,000,000) M์ด์ƒ N์ดํ•˜์˜ ์†Œ์ˆ˜๊ฐ€ ํ•˜๋‚˜ ์ด์ƒ ์žˆ๋Š” ์ž…๋ ฅ๋งŒ ์ฃผ์–ด์ง„๋‹ค. ์ถœ๋ ฅ ํ•œ ์ค„์— ํ•˜๋‚˜์”ฉ, ์ฆ๊ฐ€ํ•˜๋Š” ์ˆœ์„œ๋Œ€๋กœ ์†Œ์ˆ˜๋ฅผ ์ถœ๋ ฅํ•œ๋‹ค. ์˜ˆ์ œ ์ž…๋ ฅ 3 16 ์˜ˆ์ œ ์ถœ๋ ฅ 3 5 7 11 13 ํ’€์ด 1. ์ˆซ์ž m๊ณผ n์„ ์ž…๋ ฅ๋ฐ›์•„ n+1ํฌ๊ธฐ์˜ ๋ฐฐ์—ด์„ ์ƒ์„ฑ. ๋ฐฐ์—ด์˜ idx๊ฐ’์ด ์ˆซ์ž๋ผ๊ณ  ๊ฐ€์ •ํ•œ๋‹ค. 2..