BOJ : https://www.acmicpc.net/problem/6588

GitHub : https://github.com/junho0956/Algorithm/blob/master/6588/6588/%EC%86%8C%EC%8A%A4.cpp

 

가장 작은 홀수이자 소수인 3부터 N-3 을 해가며 짝을 찾아주면된다.

처음에 시간초과가 뜨길래 문제가 있나 싶었는데

ios::sync_with_stdio(false) 는 사용했으면서 cin.tie(NULL)을 해줘야되는지 몰랐다,, 알았으니 됬다

 

더보기
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
27
28
29
#include <iostream>
using namespace std;
#define Max 1000001
 
bool arr[Max];
 
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    for (int i = 2; i < Max; i++) arr[i] = true;
    for (int i = 2; i * i < Max; i++) {
        if (!arr[i]) continue;
        for (int k = i * i; k < Max; k += i) arr[k] = false;
    }
 
    int num;
    while (1) {
        cin >> num;
        if (!num) break;
        for (int i = 3; i < Max; i+=2) {
            if (arr[i] && arr[num - i]) {
                cout << num << " = " << i << " + " << num - i << '\n';
                break;
            }
        }
    }
 
    return 0;
}
http://colorscripter.com/info#e" target="_blank" style="color:#e5e5e5text-decoration:none">Colored by Color Scripter

'algorithm > BOJ' 카테고리의 다른 글

BOJ 10872번 팩토리얼  (0) 2020.01.13
BOJ 11653번 소인수분해  (0) 2020.01.13
BOJ 1929번 소수 구하기  (0) 2020.01.13
BOJ 1978번 소수 찾기  (0) 2020.01.13
BOJ 2089번 -2진수  (0) 2020.01.13

BOJ : https://www.acmicpc.net/problem/1929

GitHub : https://github.com/junho0956/Algorithm/blob/master/1929/1929/%EC%86%8C%EC%8A%A4.cpp

 

에라토스테네스의 체에 대한 개념을 알고있다면 해결할 수 있다.

 

더보기
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <iostream>
using namespace std;
#define Max 1000001
 
bool arr[Max];
 
int main() {
    ios::sync_with_stdio(0);
    for (int i = 2; i < Max; i++)
        arr[i] = true;
 
    for (int i = 2; i * i < Max; i++) {
        if (!arr[i]) continue;
        for (int k = i * i; k < Max; k += i) arr[k] = false;
    }
 
    int N, M;
    cin >> N >> M;
    for (int i = N; i <= M; i++) {
        if (arr[i]) cout << i << '\n';
    }
    return 0;
}
http://colorscripter.com/info#e" target="_blank" style="color:#e5e5e5text-decoration:none">Colored by Color Scripter

'algorithm > BOJ' 카테고리의 다른 글

BOJ 11653번 소인수분해  (0) 2020.01.13
BOJ 6588번 골드바흐의 추측  (0) 2020.01.13
BOJ 1978번 소수 찾기  (0) 2020.01.13
BOJ 2089번 -2진수  (0) 2020.01.13
BOJ 1212번 8진수 2진수  (0) 2020.01.13

BOJ : https://www.acmicpc.net/problem/1978

GitHub : https://github.com/junho0956/Algorithm/blob/master/1978/1978/%EC%86%8C%EC%8A%A4.cpp

 

소수를 찾기위한 정확한 개념을 기억해두자.

** 소수는 소수로 나누어떨어지지 않는다.

 

더보기
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 <iostream>
using namespace std;
 
#define MAX 1001
 
bool sosu[MAX];
 
int main() {
    for (int i = 2; i < MAX; i++) sosu[i] = true;
 
    for (int i = 2; i * i < MAX; i++) {
        if (!sosu[i]) continue;
        for (int k = i * i; k < MAX; k += i) sosu[k] = false;
    }
 
    int N,n, cnt=0; cin >> N;
 
    while (N--) {
        cin >> n;
        cnt += sosu[n];
    }
 
    cout << cnt;
    return 0;
}
http://colorscripter.com/info#e" target="_blank" style="color:#e5e5e5text-decoration:none">Colored by Color Scripter

'algorithm > BOJ' 카테고리의 다른 글

BOJ 6588번 골드바흐의 추측  (0) 2020.01.13
BOJ 1929번 소수 구하기  (0) 2020.01.13
BOJ 2089번 -2진수  (0) 2020.01.13
BOJ 1212번 8진수 2진수  (0) 2020.01.13
BOJ 1373번 2진수 8진수  (0) 2020.01.13

BOJ : https://www.acmicpc.net/problem/2089

GitHub : https://github.com/junho0956/Algorithm/blob/master/2089/2089/%EC%86%8C%EC%8A%A4.cpp

 

-2진수에 대한 변환법은 2진수 변환법과 똑같다

다른 부분은 나눗셈을 할 때 몫과 나머지를 잘 건드려줘야되는 것

13을 2로 나누면 몫은 6, 나머지는 1이다.

하지만 -13 을 2로 나누면 몫을 -6, 나머지는 -1이 되는데

이 문제를 풀기 위해서는 -13 -> -7, 1 을 만들어야하는 과정을 이해해야한다.

 

다른분들 블로그를 읽어봤는데 개념을 제대로 파악하지 않고 외우기식 문제풀이만 하는 분들이 많았다.

그렇게하면 문제를 안푼거랑 똑같지않나 라는 생각이 든다.

 

2진수라는 것은 1과 0으로만 표현할 수 있다. -1은 표현이 안되는 수이다

이 개념을 이용해보자면 ==> -1을 1로 만들수 없을까? 가 되고

-1을 1로 만들려면 몫을 -1 만큼 더 주는 대신 나머지는 2를 더해주는 것이다.

===> -13 을 2로 나누면 몫은 -7, 나머지는 1 이 된다.

이 방법을 이용하면 나머지가 1,0으로만 떨어지면서 2진수로 표현이 가능해진다.

 

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
27
28
29
#include <cstdio>
#include <stack>
using namespace std;
#pragma warning(disable:4996)
stack<int> s;
int main() {
    int N;
    scanf("%d", &N);
    if (!N) s.push(0);
    while (N) {
        if (N > 0) {
            s.push(N % 2);
            N = N / 2 * -1;
        }
        else {
            if ((N * -1) % 2 == 0) {
                s.push(0);
                N = N * -1 / 2;
            }
            else {
                s.push(1);
                N = ((N * -1) + 1) / 2;
            }
        }
    }
    while (!s.empty()) printf("%d", s.top()), s.pop();
 
    return 0;
}
http://colorscripter.com/info#e" target="_blank" style="color:#e5e5e5text-decoration:none">Colored by Color Scripter

'algorithm > BOJ' 카테고리의 다른 글

BOJ 1929번 소수 구하기  (0) 2020.01.13
BOJ 1978번 소수 찾기  (0) 2020.01.13
BOJ 1212번 8진수 2진수  (0) 2020.01.13
BOJ 1373번 2진수 8진수  (0) 2020.01.13
BOJ 2745번 진법 변환  (0) 2020.01.13

+ Recent posts

티스토리툴바