[Python] ๋ฐฑ์ค€ 2960 - ์—๋ผํ† ์Šคํ…Œ๋„ค์Šค์˜ ์ฒด
ยท
Algorithm
๋ฌธ์ œ ์—๋ผํ† ์Šคํ…Œ๋„ค์Šค์˜ ์ฒด๋Š” N๋ณด๋‹ค ์ž‘๊ฑฐ๋‚˜ ๊ฐ™์€ ๋ชจ๋“  ์†Œ์ˆ˜๋ฅผ ์ฐพ๋Š” ์œ ๋ช…ํ•œ ์•Œ๊ณ ๋ฆฌ์ฆ˜์ด๋‹ค. ์ด ์•Œ๊ณ ๋ฆฌ์ฆ˜์€ ๋‹ค์Œ๊ณผ ๊ฐ™๋‹ค. 2๋ถ€ํ„ฐ N๊นŒ์ง€ ๋ชจ๋“  ์ •์ˆ˜๋ฅผ ์ ๋Š”๋‹ค. ์•„์ง ์ง€์šฐ์ง€ ์•Š์€ ์ˆ˜ ์ค‘ ๊ฐ€์žฅ ์ž‘์€ ์ˆ˜๋ฅผ ์ฐพ๋Š”๋‹ค. ์ด๊ฒƒ์„ P๋ผ๊ณ  ํ•˜๊ณ , ์ด ์ˆ˜๋Š” ์†Œ์ˆ˜์ด๋‹ค. P๋ฅผ ์ง€์šฐ๊ณ , ์•„์ง ์ง€์šฐ์ง€ ์•Š์€ P์˜ ๋ฐฐ์ˆ˜๋ฅผ ํฌ๊ธฐ ์ˆœ์„œ๋Œ€๋กœ ์ง€์šด๋‹ค. ์•„์ง ๋ชจ๋“  ์ˆ˜๋ฅผ ์ง€์šฐ์ง€ ์•Š์•˜๋‹ค๋ฉด, ๋‹ค์‹œ 2๋ฒˆ ๋‹จ๊ณ„๋กœ ๊ฐ„๋‹ค. N, K๊ฐ€ ์ฃผ์–ด์กŒ์„ ๋•Œ, K๋ฒˆ์งธ ์ง€์šฐ๋Š” ์ˆ˜๋ฅผ ๊ตฌํ•˜๋Š” ํ”„๋กœ๊ทธ๋žจ์„ ์ž‘์„ฑํ•˜์‹œ์˜ค. ์ž…๋ ฅ ์ฒซ์งธ ์ค„์— N๊ณผ K๊ฐ€ ์ฃผ์–ด์ง„๋‹ค. (1 ≤ K < N, max(2, K) < N ≤ 1000) ์ถœ๋ ฅ ์ฒซ์งธ ์ค„์— K๋ฒˆ์งธ ์ง€์›Œ์ง„ ์ˆ˜๋ฅผ ์ถœ๋ ฅํ•œ๋‹ค. ์ •๋‹ต n, k = map(int, input().split()) ch = [0]*(n+1) count = 0 result =..