글 읽기 - [2436번_공약수] 어디가 잘못된 걸까요..?

dlsxor48 7년 전 0

안녕하세요~ 알고리즘 문제풀이 초보 대학생입니다.

제가 작성한 2436번 공약수 문제 소스에서 어느 부분이 잘못된 걸까요..?ㅠㅜ

떠오르는 숫자들을 모두 대입해봐도 올바른 값이 나오는 것 같은데 자꾸 '틀렸습니다'라고 판정이 되네요ㅠㅜ

혼자서는 도저히 잘못된 부분을 못찾겠어서 질문드립니다.

-소스 로직

최대공약수와 최소공배수가 주어지고 이 값들이 구성될 수 있는 개별 값들을 구하기 위해, 사용자로부터 입력받은 최소공배수 값의 약수들을 구했습니다. 그 후 이 값들 중 최대공약수로 나누어 떨어지는 값들을 추렸습니다. 이 추려진 값들 중 2개의 조합을 구성하여 이 값들의 최소공배수가 input의 최소공배수 값이 되는 경우 정답 후보로 저장하는 방식으로 구현했습니다.

-소스 내부 동작

input으로 입력받은 lcm의 약수들을 구한 후 (이를 arrDivisor[] 배열에 저장), 이 값들 중 input으로 받은 gcd값으로 나누어 떨어지는(정답의 가능성이 있는) 값들을 nominee[] 배열에 저장하였습니다.

그리고 이 nominee[] 배열들에서 구성 가능한 모든 2개 값의 조합들을 checkLCM() 함수를 통해, 두 수의 최소공배수가 input으로 받은 lcm과 같은지를 확인 후, 값이 같으면서 두 값의 합이 기존에 찾은 두 개의 합보다 작은 경우 arr[] 배열에 저장하도록 작성했습니다.

맨 처음 최소공배수의 약수들 중에서 추려내는 방식이 잘못된 것일까요?

아니면 소스에서 예외케이스가 발생하는 부분이 있는 것일까요?

아시는 분 계시면 도움 부탁드립니다!ㅠㅜ

#include<iostream>
#include<algorithm>
#include<limits.h>

#define FALSE 0
#define TRUE 1

using namespace std;
 
int lcm, gcd;
int arrDivisor[10000000] = {0, };
int nominee[10000000] = {0, };

void swap(int* a, int* b) {
	int temp;
	
	temp = *a;
	*a = *b;
	*b = temp;
}


int getGCD(int a, int b) { // 유클리드 호제법
	if(a < b)
		swap(a, b);

	while (a % b != 0) {
        int tmp = a;      
        a = b;                
        b = tmp % b;
    }

    return b;

}


int checkLCM(int a, int b) { // 매개변수 a, b의 최소공배수 값이 
                             // input으로 입력받은 lcm 값과 동일한지 확인하기 위한 함수
    
	int tempGCD = getGCD(a, b);

	if(tempGCD != gcd)
		return FALSE;
	else 
	{
		if( (a*b / gcd) == lcm )
			return TRUE;
		else
			return FALSE;
	}

}

void getDivisor(int num) { // 매개변수 num의 약수를 구하여 arrDivisor[] 배열에 저장

	int j = 0;

	for(int i = 1; i*i < num; i++) {
		if(num % i == 0) {
			arrDivisor[j++] = i;
			arrDivisor[j++] = num / i;
		}
	}		
}

int main() {
	
	int arr[3] = {0, 0, INT_MAX}; // 정답가능 후보 저장(arr[0], arr[1]), 이 두 값의 합 저장(arr[2])

	cin >> gcd >> lcm;

	getDivisor(lcm);
	
	int idx = 0;
	int idx2 = 0;
	
	while(arrDivisor[idx] != 0) {
		if(arrDivisor[idx] % gcd == 0)
			nominee[idx2++] = arrDivisor[idx];
		idx++;
	}

	for(int i = 0; i < idx2 - 1; i++) {
		for(int j = 1; j < idx2; j++) {
			if( checkLCM(nominee[i], nominee[j]) )
				if(arr[2] > nominee[i] + nominee[j]) {
					arr[0] = nominee[i];
					arr[1] = nominee[j];
					arr[2] = arr[0] + arr[1];
				}
        }
    }

	if(arr[0] > arr[1])
		swap(arr[0], arr[1]);

	cout << arr[0] << " " << arr[1];

	return 0;
}

ntopia 7년 전 1

getDivisor 함수 구현이 문제인 것 같네요.

num 인자로 9를 넘기면 약수 리스트에 3이 들어가지 않습니다.

제곱수인 경우 문제가 되네요.

dlsxor48 7년 전 0

감사합니다!

getDivisor 함수에도 문제가 있었네요ㅠ

근데 다른 부분도 문제가 있나봐요...

getDivisor() 함수 부분 수정해서 말씀해주신 문제 해결하고, 중복 값이 nominee에 들어가지 않도록 구현했는데도 자꾸 틀리네요..ㅠㅜ

void getDivisor(int num) { // 매개변수 num의 약수를 구하여 arrDivisor[] 배열에 저장

	int j = 0;

	for(int i = 1; i*i <= num; i++) {
		if(num % i == 0) {
			arrDivisor[j++] = i;
			if(i != num/i )
				arrDivisor[j++] = num / i;
		}
	}		
}

or
    
void getDivisor(int num) { // 매개변수 num의 약수를 구하여 arrDivisor[] 배열에 저장

	int j = 0;

	for(int i = 1; i <= num; i++) {
		if(num % i == 0) {
			arrDivisor[j++] = i;
			if(i != num/i )
				arrDivisor[j++] = num / i;
		}
	}		
}

ntopia 7년 전 0

78~82번째 줄에 arrDivisor를 하나씩 훑는 부분에서

실제로 약수가 존재하는 부분까지만 진행하도록 제한해야할 것 같습니다.

약수가 존재하는 부분을 넘어서면 arrDivisor[idx] 가 0이기 때문에

arrDivisor[idx] % gcd == 0 가 항상 참이 됩니다.

ntopia 7년 전 1

checkLCM 함수에서

a * b 를 한 후에 gcd로 나누는데,

문제 입력조건을 보면 a * b에서 오버플로우가 발생할 수 있습니다.

long long 을 쓰는게 좋을 것 같습니다.

dlsxor48 7년 전 0

감사합니다.

line 78~82 부분에서는 while문의 조건문이 말씀해주신 실제 약수가 존재하는 부분까지 제한을 두도록 동작하는 것 같아서 그대로 뒀습니다.
arrDivisor[] 배열의 초기값이 0으로 설정되어있고, getDivisor() 함수를 거치면 모든 input값에서 최소 2개의 arrDivisor[] 값이 저장되므로, while문의 조건문 부분 '(arrDivisor[idx] != 0)'이 그 역할을 하고 있는 것 같아서요~

overflow 방지하려고 checkLCM() 함수 내부에서 임시적으로 형변환을 해 줬는데... 또 다시.. 실패네요..ㅠㅜ

생각 못했던 부분들 얘기해주셔서 고치고 들인 시간도 적지않아서 ..꼭 맞추고 싶은데.. ㅋㅋㅋㅋ 다른데도 문제가 있나봅니다..ㅠㅜ

int checkLCM(int a, int b) { // 매개변수 a, b의 최소공배수 값이 
                             // input으로 입력받은 lcm 값과 동일한지 확인하기 위한 함수
    
	int tempGCD = getGCD(a, b);

	if(tempGCD != gcd)
		return FALSE;
	else 
	{
		if( ((long long int)a*(long long int)b / gcd) == lcm )
			return TRUE;
		else
			return FALSE;
	}

}

ntopia 7년 전 1

입력으로 주어지는 gcd와 lcm이 같은 경우에 0 0을 출력하고 끝나네요

4 4 같은 입력 넣어서 디버깅 해보세요...

dlsxor48 7년 전 0

ntopia 님 정말 감사합니다!!

두 값이 동일한 경우 처리하는 부분 넣어주니 정답이네요 ㅎㅎㅎ

귀찮은 질문 계속 받아주셔서 감사합니다. 수고하세요^^

int main() {
	
	int arr[3] = {0, 0, INT_MAX}; // 정답가능 후보 저장(arr[0], arr[1]), 이 두 값의 합 저장(arr[2])

	cin >> gcd >> lcm;

	if(gcd == lcm) {
		cout << gcd << " " << lcm;
		return 0;
	}

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

문제

문제

출처

ICPC

[2436번_공약수] 어디가 잘못된 걸까요..?

dlsxor48 7년 전 0

ntopia 7년 전 1

dlsxor48 7년 전 0

ntopia 7년 전 0

ntopia 7년 전 1

dlsxor48 7년 전 0

ntopia 7년 전 1

dlsxor48 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말