๋ณธ๋ฌธ ๋ฐ”๋กœ๊ฐ€๊ธฐ
๐Ÿ”ฅ PS(Problem Solving) ๐Ÿ”ฅ/BOJ

[BOJ] #6359 ๋งŒ์ทจํ•œ ์ƒ๋ฒ”

by dar0m! 2019. 9. 19.
์‹œ๊ฐ„ ์ œํ•œ ๋ฉ”๋ชจ๋ฆฌ ์ œํ•œ ์ •๋‹ต ๋น„์œจ
 1 ์ดˆ  128 MB 69.799 %

 

 

6359๋ฒˆ: ๋งŒ์ทจํ•œ ์ƒ๋ฒ”

๋ฌธ์ œ ์„œ๊ฐ•๋Œ€ํ•™๊ต ๊ณค์ž๊ฐ€ ๊ธฐ์ˆ™์‚ฌ์˜ ์ง€ํ•˜์—๋Š” n๊ฐœ์˜ ๋ฐฉ์ด ์ผ๋ ฌ๋กœ ๋Š˜์–ด์„  ๊ฐ์˜ฅ์ด ์žˆ๋‹ค. ๊ฐ ๋ฐฉ์—๋Š” ๋ฒŒ์ ์„ ๋งŽ์ด ๋ฐ›์€ ํ•™์ƒ์ด ๊ตฌ๊ธˆ๋˜์–ด์žˆ๋‹ค. ๊ทธ๋Ÿฌ๋˜ ์–ด๋Š ๋‚ , ๊ฐ์˜ฅ ๊ฐ„์ˆ˜์ธ ์ƒ๋ฒ”์ด๋Š” ์ง€๋ฃจํ•œ ๋‚˜๋จธ์ง€ ์ •์‹ ๋‚˜๊ฐ„ ๊ฒŒ์ž„์„ ํ•˜๊ธฐ๋กœ ๊ฒฐ์ •ํ–ˆ๋‹ค. ๊ฒŒ์ž„์˜ ์ฒซ ๋ฒˆ์งธ ๋ผ์šด๋“œ์—์„œ ์ƒ๋ฒ”์ด๋Š” ์œ„์Šคํ‚ค๋ฅผ ํ•œ ์ž” ๋“ค์ดํ‚ค๊ณ , ๋‹ฌ๋ ค๊ฐ€๋ฉฐ ๊ฐ์˜ฅ์„ ํ•œ ๊ฐœ์”ฉ ๋ชจ๋‘ ์—ฐ๋‹ค. ๊ทธ ๋‹ค์Œ ๋ผ์šด๋“œ์—์„œ๋Š” 2, 4, 6, ... ๋ฒˆ ๋ฐฉ์„ ๋‹ค์‹œ ์ž ๊ทธ๊ณ , ์„ธ ๋ฒˆ์งธ ๋ผ์šด๋“œ์—์„œ๋Š” 3, 6, 9, ... ๋ฒˆ ๋ฐฉ์ด ์—ด๋ ค์žˆ์œผ๋ฉด ์ž ๊ทธ๊ณ 

www.acmicpc.net

๋ฌธ์ œ

n๊ฐœ์˜ ๋ฐฉ์ด ์ผ๋ ฌ๋กœ ๋Š˜์–ด์„  ๊ฐ์˜ฅ์ด ์žˆ๋‹ค. ๊ฐ ๋ฐฉ์—๋Š” ๋ฒŒ์ ์„ ๋งŽ์ด ๋ฐ›์€ ํ•™์ƒ์ด ๊ตฌ๊ธˆ๋˜์–ด์žˆ๋‹ค.

์ฒซ ๋ฒˆ์งธ ๋ผ์šด๋“œ์—์„œ ์ƒ๋ฒ”์ด๋Š” ๋ชจ๋“  ๊ฐ์˜ฅ์„ ํ•œ ๊ฐœ์”ฉ ๋ชจ๋‘ ์—ฐ๋‹ค. ๊ทธ ๋‹ค์Œ ๋ผ์šด๋“œ์—์„œ๋Š” 2, 4, 6, ... ๋ฒˆ ๋ฐฉ์„ ๋‹ค์‹œ ์ž ๊ณก, ์„ธ ๋ฒˆ์งธ ๋ผ์šด๋“œ์—์„œ๋Š” 3, 6, 9, ... ๋ฒˆ ๋ฐฉ์ด ์—ด๋ ค์žˆ์œผ๋ฉด ์ž ๊ทธ๊ณ , ์ž ๊ฒจ์žˆ๋‹ค๋ฉด ์—ฐ๋‹ค. k๋ฒˆ์งธ ๋ผ์šด๋“œ์—์„œ๋Š” ๋ฒˆํ˜ธ๊ฐ€ k์˜ ๋ฐฐ์ˆ˜์ธ ๋ฐฉ์ด ์—ด๋ ค ์žˆ์œผ๋ฉด ์ž ๊ทธ๊ณ , ์ž ๊ฒจ ์žˆ๋‹ค๋ฉด ์—ฐ๋‹ค. ์ด๋ ‡๊ฒŒ n๋ฒˆ์งธ ๋ผ์šด๋“œ๊นŒ์ง€ ์ง„ํ–‰ํ•œ ์ดํ›„, ์ƒ๋ฒ”์ด๋Š” ์œ„์Šคํ‚ค์˜ ๋งˆ์ง€๋ง‰ ๋ณ‘์„ ๋งˆ์‹œ๊ณ  ์“ฐ๋Ÿฌ์ ธ ์ž ๋“ ๋‹ค.

๊ตฌ๊ธˆ๋˜์–ด์žˆ๋Š” ๋ช‡ ๋ช…(์–ด์ฉŒ๋ฉด 0๋ช…)์˜ ํ•™์ƒ๋“ค์€ ์ž์‹ ์˜ ๋ฐฉ์„ ์ž ๊ทธ์ง€ ์•Š์€ ์ฑ„ ์ƒ๋ฒ”์ด๊ฐ€ ์“ฐ๋Ÿฌ์ ธ๋ฒ„๋ ธ๋‹จ ๊ฒƒ์„ ๊นจ๋‹ซ๊ณ  ์ฆ‰์‹œ ๋„๋ง์นœ๋‹ค.

๋ฐฉ์˜ ๊ฐœ์ˆ˜๊ฐ€ ์ฃผ์–ด์กŒ์„ ๋•Œ, ๋ช‡ ๋ช…์˜ ํ•™์ƒ๋“ค์ด ๋„์ฃผํ•  ์ˆ˜ ์žˆ๋Š”์ง€ ์•Œ์•„๋ณด์ž.

์ž…๋ ฅ

์ž…๋ ฅ์˜ ์ฒซ ๋ฒˆ์งธ ์ค„์—๋Š” ํ…Œ์ŠคํŠธ ์ผ€์ด์Šค์˜ ๊ฐœ์ˆ˜ T๊ฐ€ ์ฃผ์–ด์ง„๋‹ค. ๊ฐ ํ…Œ์ŠคํŠธ ์ผ€์ด์Šค๋Š” ํ•œ ์ค„์— ํ•œ ๊ฐœ์”ฉ ๋ฐฉ์˜ ๊ฐœ์ˆ˜ n(5 โ‰ค n โ‰ค 100)์ด ์ฃผ์–ด์ง„๋‹ค.

 

๋ฉ”๋ชจ๋ฆฌ ์‹œ๊ฐ„
1999 KB 0 ms
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
int t, n, ans;
int prison[105];
int main() {
    scanf("%d"&t);
    while (t--) {
        scanf("%d"&n);
        for (int i = 2; i <= n; i++) {
            for (int j = i; j <= n; j += i) {
                prison[j] = prison[j] ? 0 : 1;
            }
        }
        for (int i = 1; i <= n; i++) {
            if (!prison[i]) ans++;
        }
        printf("%d\n", ans);
        ans = 0;
        memset(prison, 0sizeof(prison));
    }
    
    return 0;
}
cs

 

๋ ์š”์˜ค์˜น
์ข€ ๋งŒ ์ƒ๊ฐํ•˜๋ฉด ์ด๋ ‡๊ฒŒ ๋‚˜์˜จ๋‹ต๋‹ˆ๋‹ค ^^.. ๋ฃจํŠธ ๊ฐ’์ด๋„ค..... ์ด ๋ถ€๋ถ„์€ ๋‹ค์Œ ์ฃผ ์Šคํ„ฐ๋”” ํ•  ๋•Œ ์˜๋…ผํ•˜๊ธฐ..

1
2
3
4
5
6
7
8
9
10
#include<stdio.h>
int main() {
    int i, t, n; scanf("%d"&t);
    while (t--) {
        scanf("%d"&n);
        for (i = 1; i*<= n; i++);
        printf("%d\n", i-1);
    }
    return 0;
}
cs

'๐Ÿ”ฅ PS(Problem Solving) ๐Ÿ”ฅ > BOJ' ์นดํ…Œ๊ณ ๋ฆฌ์˜ ๋‹ค๋ฅธ ๊ธ€

[BOJ] #3190 ๋ฑ€  (0) 2019.09.29
[BOJ] #16929 Two Dots  (0) 2019.09.29
[BOJ] #14501 ํ‡ด์‚ฌ  (0) 2019.09.19
[BOJ] #2309 ์ผ๊ณฑ ๋‚œ์Ÿ์ด  (0) 2019.09.19
[BOJ] #14888 ์—ฐ์‚ฐ์ž ๋ผ์›Œ๋„ฃ๊ธฐ  (0) 2019.09.04

๋Œ“๊ธ€