글 읽기 - [C++] 출력되는 벡터를 long long 으로 설정했는데 안 되는 이유?

cequala 3년 전 0

첫 시도에서는 메인함수에 있는 벡터 s를 int로 설정했습니다. s는 최대공약수의 합들을 담는 벡터로, 마지막 for문에서 이들을 차례로 출력하게 됩니다. 그런데 70%까지 채점이 되다가 틀려버려서, 질문글을 검색하다 총합들이 int의 범위를 넘어서는 경우를 고려해야 한다는 것을 알게 되었습니다.

하여 s를 long long으로 설정하고 재시도를 해보니, 아예 처음부터 틀렸다고 나오네요... 초기 시도에서 채점이 좀 됐기 때문에 자료형 선언에 대한 문제로 확신했는데, 혹시 다른 문제일까요?

#include <iostream>
#include <vector>
#include <numeric>
using namespace std;

int gcd(int a, int b) { // Euclidean
	int r = a % b;
	if (r == 0) {
		return b;
	}
	else {
		return gcd(b, r);
	}
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);

	int t, n, N;
	cin >> t;
	vector<int> v, g;
    vector<long long> s;
    // vector<int> s;로 했을때는 적어도 70%까지 채점됨

	for (int i = 0; i < t; i++) {
		cin >> n;
		for (int j = 0; j < n; j++) {
			cin >> N;
			v.push_back(N);
		}
		for (int j = 0; j < v.size() - 1; j++) {
			for (int k = 0; k < v.size(); k++) {
				if (k > j) {
					g.push_back(gcd(v[j], v[k]));
				}
			}
		}
		s.push_back(accumulate(g.begin(), g.end(), 0)); // g총합
		g.clear(); // g 초기화
		v.clear(); // v 초기화
	}
	for (int i = 0; i < s.size(); i++) {
		cout << s[i] << '\n';
	}
	return 0;
}

cequala 3년 전 0

여기 해답 적어주신 분이 왜 댓글을 지웠을까요;; 39줄의 0을 0LL로 바꾸면 정답처리됩니다!

cequala 3년 전 0

GCD는 Great common divider의 약자로, 최대공약수를 뜻합니다. 최대공약수가 무엇인지는 구글에 찾아보는 게 빠를 겁니다. 제가 처음에 헷갈렸던 부분은 문제 설명인데, 예시를 보면 입력되는 수 중에서 가능한 두 수의 쌍을 모두 구한 다음에, 각 쌍마다의 최대공약수를 구하고, 그렇게 나온 최대공약수를 모두 더한 것이 출력임을 알 수 있습니다.

예컨대 예시의 입력 중 하나인 4 10 20 30 40을 보면, 맨 처음 4는 그 다음에 10 20 30 40의 4가지 수가 나온다는 것을 뜻합니다. 이 4가지 수 중에서 가능한 두 수의 쌍은 (10, 20), (10, 30), (10, 40), (20, 30), (20, 40), (30, 40)가 있죠. 그리고 수 a, b로 이뤄진 쌍의 최대공약수를 gcd(a, b)라 둡시다. 그러면 gcd(10, 20)=10, gcd(10, 30)=10, gcd(10, 40)=10, gcd(20, 30)=10, gcd(20, 40)=20, gcd(30, 40)=10이 됩니다. 이렇게 나온 모든 최대공약수를 다 더하면 10+10+10+10+20+10=70으로 예시의 출력과 같죠.

duino03 3년 전 0

길게 설명해주셨군요 사실 최대공약수라는건 알고리즘 보면서 알았는데 gcd가 Great common divider 약자인건 처음알았습니다

문제는 뭔말인지는 이해한 상태여서 안적으셔도 되는데.. 덕분에 머릿속에 박히게 되네요 바쁜시간 내주셔서 감사합니다

정말정말 감사합니다ㅏㅏ

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

문제

문제

출처

ICPC

[C++] 출력되는 벡터를 long long 으로 설정했는데 안 되는 이유?

cequala 3년 전 0

cequala 3년 전 0

duino03 3년 전 0

duino03 3년 전 0

cequala 3년 전 0

duino03 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말