우주의WouldYou

이 문제도 시간초과가 나서 당황스러웠던 문제,,,,, 답은 제대로 나오는데 어떻게 풀어야할까 고민하다가,,

검색을 해보니 cin, cout과 printf, scanf의 속도차이가 크다고 해서 일단 cin만 scanf로 수정을 해주었더니 바로 맞았습니다, 가 떴다.

속도를 위해선 scanf와 printf를 써야함을 잊지 말자!

#include <iostream>
using namespace std;
bool check[1000001];

int main() {
    int num, i, j, tmp, flag = 0;

    check[0] = check[1] = true;

    for (i = 2; i < 1000001; i++) {
        if (check[i] == false) {
            for (j = i * 2; j < 1000001; j += i)
                check[j] = true;
        }
    }

    scanf("%d", &num);
    while (num != 0) {
         for (i = 3; i < num/2 + 1; i++) {
             if (check[i] == false) {
                  tmp = num - i;
                  if (tmp>0 && check[tmp] == false) {
                       cout << num << " = " << i << " + " << tmp << '\n';
                       flag = 1;
                       break;
                  }
            }
        }
        if (flag == 0)
             cout << "Goldbach's conjecture is wrong.\n";
        scanf("%d", &num);
    }

}

원래 check를 int배열로 만들었는데, 계속 시간 초과가 나서,,

bool로 바꿔주었더니 아주 빠르게 되었다...

#include <iostream>
using namespace std;


bool check[1000001];
int main() {

    int i, j, M, N;
    check[0] = check[1] = true;

    for (i = 2; i < 1000001; i++) {
    if (check[i]==false) {
        for (j = i * 2; j < 1000001; j += i)
            check[j] = true;
        }
    }

    cin >> M >> N;
    for (i = M; i < N+1; i++) {
        if (check[i] == false)
             cout << i << '\n';
    }
}

아 내 논리로는 정말 무조건 맞는데 왜 틀렸는지를 한참 고민한 문제다....

역시나 이번에도 문제를 제대로 읽지 않아서 틀렸다......

바로 어제, 문제를 제대로 읽자고 다짐했는데 오늘도 그래서 틀리다니,,흑흑

자꾸 틀렸습니다, 가 나와서 고민했는데,,그 이유는 범위가 1000까지 인데 나는 100까지로 줘서 그렇다....

문제를 제대로 읽자 제발!!

#include  <iostream>
using namespace std;

int check[1001] = { 0 };
int main() {
    int tmp, total, i, k, prime_cnt = 0, prime;
    long long j;

    check[1] = 1;

    for (i = 2; i < 1001; i++) {
        if (!check[i]) {

            for (j = i * 2; j < 1001; j +=i) 
                check[j] = 1;

        }
    }

    cin >> total;

    for (i = 0; i < total; i++) {
        cin >> tmp;
        if (!check[tmp])
            prime_cnt++;
    }
    cout << prime_cnt << endl;
}

이 문제의 경우 잘못 이해해서 처음에 헤매었다..

오늘의 교훈: 문제를 차분히 읽고 구상해본 다음 작성하기!

왜냐하면 예시로 주어진 것만 보다가 엔터 치면 입력 종료하는 거라고 받아들여서 완전 이상하게 짜고 있었기 때문이다..

아스키 코드 이용해서 하는 건줄알고 그렇게 해봤는데 안되길래 찾아봤더니 cin/scanf의 경우 엔터를 쳤다고 해도 입력의 종료라는 의미 보다는 입력의 대기의미로 받아들이기 때문이라고 한다...

아무튼 문제를 잘 이해하고 난 후 다시 잘 풀었는데, 또 한 번의 문제가 발생했다.

틀렸습니다, 가 나와서 당황스러웠는데,

이 경우는 sum이 자료형이 처음엔 int로 되어 있던 것이 문제가 되었다. long long으로 수정한 뒤 해결하였다.

#include <iostream>
using namespace std;

int GCD(int a, int b) {
    if (b == 0)
        return a;
    while (b != 0)
        return GCD(b, a%b);
}
int main() {
    int lines, i, n, j, k;
    long long gcd_sum;

    cin >> lines;
    for (i = 0; i < lines; i++) {
        int testcase[100] = { 0 };
        gcd_sum = 0;
        cin >> n;
        for(j =0; j < n; j++) {
            cin >> testcase[j];
        }
        for (j = 0; j <n-1; j++) {
            for ( k = j + 1; k <n; k++) {
                gcd_sum += GCD(testcase[j], testcase[k]);
            }
        }
        cout << gcd_sum << endl;
    }
}