dlsxor48   4달 전

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

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

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

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


-소스 로직

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


-소스 내부 동작

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

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


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

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

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

ntopia   4달 전

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

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

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

dlsxor48   4달 전

감사합니다!

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

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

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




ntopia   4달 전

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

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

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

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

ntopia   4달 전

checkLCM 함수에서 

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

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

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

dlsxor48   4달 전

감사합니다.


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


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


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

ntopia   4달 전

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

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

dlsxor48   4달 전

ntopia 님 정말 감사합니다!!

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

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

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