-
[๋ฐฑ์ค(BOJ)] 2960๋ฒ ์๋ผํ ์คํ ๋ค์ค์ ์ฒด, C์ธ์ด ํ์ดPS(Problem Solving)/C 2020. 8. 4. 14:05๋ฐ์ํ
<์๋ผํ ์คํ ๋ค์ค์ ์ฒด>, 2960๋ฒ
๋ฌธ์
์๋ผํ ์คํ ๋ค์ค์ ์ฒด๋ N๋ณด๋ค ์๊ฑฐ๋ ๊ฐ์ ๋ชจ๋ ์์๋ฅผ ์ฐพ๋ ์ ๋ช ํ ์๊ณ ๋ฆฌ์ฆ์ด๋ค.
์ด ์๊ณ ๋ฆฌ์ฆ์ ๋ค์๊ณผ ๊ฐ๋ค.
-
2๋ถํฐ N๊น์ง ๋ชจ๋ ์ ์๋ฅผ ์ ๋๋ค.
-
์์ง ์ง์ฐ์ง ์์ ์ ์ค ๊ฐ์ฅ ์์ ์๋ฅผ ์ฐพ๋๋ค. ์ด๊ฒ์ P๋ผ๊ณ ํ๊ณ , ์ด ์๋ ์์์ด๋ค.
-
P๋ฅผ ์ง์ฐ๊ณ , ์์ง ์ง์ฐ์ง ์์ P์ ๋ฐฐ์๋ฅผ ํฌ๊ธฐ ์์๋๋ก ์ง์ด๋ค.
-
์์ง ๋ชจ๋ ์๋ฅผ ์ง์ฐ์ง ์์๋ค๋ฉด, ๋ค์ 2๋ฒ ๋จ๊ณ๋ก ๊ฐ๋ค.
N, K๊ฐ ์ฃผ์ด์ก์ ๋, K๋ฒ์งธ ์ง์ฐ๋ ์๋ฅผ ๊ตฌํ๋ ํ๋ก๊ทธ๋จ์ ์์ฑํ์์ค.
์ ๋ ฅ
์ฒซ์งธ ์ค์ N๊ณผ K๊ฐ ์ฃผ์ด์ง๋ค. (1 ≤ K < N, max(2, K) < N ≤ 1000)
์ถ๋ ฅ
์ฒซ์งธ ์ค์ K๋ฒ์งธ ์ง์์ง ์๋ฅผ ์ถ๋ ฅํ๋ค.
์์ ์ ๋ ฅ 1 ๋ณต์ฌ
10 7
์์ ์ถ๋ ฅ 1 ๋ณต์ฌ
9
ํ์ด
์ด ๋ฌธ์ ๋ ์์๋ฅผ ์ฐพ๋ ์๊ณ ๋ฆฌ์ฆ์ธ ์๋ผํ ์คํ ๋ค์ค์ ์ฒด๋ฅผ ์ดํดํด์ผ ํ ์ ์๋ ๋ฌธ์ ์ด๋ค. ์๋ผํ ์คํ ๋ค์ค์ ์ฒด์ ๋ํ ์ค๋ช ์ ๋ฌธ์ ์ ์ค๋ช ๋์ด ์๋ค. ๋ง๋ก ํ์ด์ ์ค๋ช ํ๋ ๊ฒ ๋ณด๋ค๋ ์์ค์ฝ๋๋ฅผ ๋ณด๊ณ ์ดํด ํ๋๊ฒ ๋ ๋์์ด ๋ ๊ฒ ๊ฐ์ ํ์ด๋ ์๋ตํ๋ค.
#include <stdio.h> int main(void) { int num[1000]; int K; int N; int count = 0; scanf("%d %d", &N, &K); for (int i = 2; i <= N; i++) num[i] = i; for (int i = 2; i <= N; i++) { if (num[i] == 0) continue; else { for (int j = i; j <= N; j += i) { if (num[j] != 0) { num[j] = 0; count++; } if (count == K) { printf("%d", j); break; } } } } return 0; }
๋ฐ์ํ -