글 읽기 - 반례 부탁드립니다...

potatocake 2년 전 0

제가 파이썬이 주력이라 코드가 좀 더럽습니다..

정수 N을 받았을 때,

N(짝수)이 짝수+짝수로 이루어진 경우, -> 각각의 짝수에 대해 골드바흐 적용

N(짝수)이 홀수+홀수로 이루어진 경우, -> (홀수+1)+(홀수-1)로 고쳐서 각각 골드바흐 적용

N이 홀수인 경우, -> N = (N-5) + 2 + 3으로 변형 후 N-5에 대해 골드바흐 적용

이런 아이디어로 풀었습니다.

#include <iostream>

const long long RANGE = 100000002;
bool sieve[RANGE];

int main(){
    long long n = 0;
    long long k = 0;

    for (long long i = 2; i*i <= RANGE; i++){
        if (!sieve[i]){
            for (long long j = i*i; j <= RANGE; j += i){
                sieve[j] = true;
            }
        }
    }

    while (scanf("%lld", &n) != EOF){
    long long ans[4] = {0};
        if (n < 8){
            printf("Impossible.\n");
        }
        else {
            if (n % 2 == 1){
                k = n - 5;
                ans[0] = 2;
                ans[1] = 3;
                for (long long i = 2; i <= k; i++){
                    if (!sieve[i] && !sieve[k-i]){
                        ans[2] = i;
                        ans[3] = k - i;
                        break;
                    }
                }
                printf("%lld %lld %lld %lld\n", ans[0], ans[1], ans[2], ans[3]);
            }
            else if (n % 4 == 0){
                k = n / 2;
                for (long long i = 2; i <= k; i++){
                    if (!sieve[i] && !sieve[k-i]){
                        ans[0] = ans[1] = i;
                        ans[2] = ans[3] = k - i;
                        break;
                    }
                }    
                printf("%lld %lld %lld %lld\n", ans[0], ans[1], ans[2], ans[3]);
            }
            else {
                long long k1 = n / 2 - 1;
                long long k2 = n / 2 + 1;
                for (long long i = 2; i <= k1; i++){
                    if (!sieve[i] && !sieve[k-i]){
                        ans[0] = i;
                        ans[1] = k1 - i;
                        break;
                    }
                }    
                for (long long i = 2; i <= k2; i++){
                    if (!sieve[i] && !sieve[k2-i]){
                        ans[2] = i;
                        ans[3] = k2 - i;
                        break;
                    }
                }    
                printf("%lld %lld %lld %lld\n", ans[0], ans[1], ans[2], ans[3]);
            }
        }
    }
    
    return 0;
}

leonhard 2년 전 1

마지막 else 부분에서 !sieve[k-1]이 아니라 !sieve[k1-1]이 되어야하지 않을까요.

potatocake 2년 전 0

감사합니다ㅠㅠ

이걸 놓쳤었네요....

코드 보시느라 정말 힘드셨을텐데 죄송하고 감사합니다ㅠㅠ

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

반례 부탁드립니다...

potatocake 2년 전 0

leonhard 2년 전 1

potatocake 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말