wjdwldud4190   3년 전

안녕하세요. 귀한시간 내서 봐주셔서 너무 감사합니다.

이 문제를 풀때 제가 생각한 알고리즘은 

만약 예제가 

3

2 3 5

2

4 5

라고 한다면 각각 인자마다 체크배열을 만들어 체크를 한 후 개수를 저장하는 것입니다. 저 위의 예제를 이용한다면

check1, check2배열, a,b배열을 이용하겠습니다. 

먼저, 각각 인자를 소인수 분해합니다. 위의 첫번째입력 인자들은 이미 소수이므로 소인수분해를 거치지 않아도 되겠네요.

두번째 입력 인자들은 4 = 2*2로 소인수 분해되어 2 2 5로 이용할 것입니다.

첫 번째 입력이 2 3 5이므로 check1[2] = 1, check1[3] = 1, check1[5] = 1를 해주고 a[2] +=1, a[3] +=1, a[5] +=1

두 번째 입력이 4 5(=2 2 5)이므로 check2[2] = 2,  check2[5] = 1를 해주고 b[2] +=2, b[5] +=1일 것입니다. 

두 수의 최대 공약수란 공통된 인자들의 곱이므로 

(check1[i]==1 & check2[i]==1)인 것들 중에서 a[i] b[i]의 공통된 숫자 만큼 곱해주는 것으로 구했습니다. 

a[2] = 1, b[2] =2이므로 2가 1개 공통 

a[5] = 1, b[5] = 1이므로 5가 1개 공통 => 2*5 =10

수가 많이 크기 때문에 소인수 분해하여 인자들을 따로 계산하는게 빠르다는 생각하에 했습니다. 

하지만 계속해서 런타임 에러가 나서 배열 인덱스를 최대한으로 키워보고 잘못된 접근을 한것은 아닌지 디버깅 해보았지만 제 실력으론 부족하네요..

혹시 비슷한 고민을 하셧거나 아신다면 제가 놓친 부분이나 잘못된 부분을 가르쳐주시면 감사하겠습니다..ㅜㅜ 

시간내주셔서 감사합니다. 

 

bupjae   3년 전

입력될 수 있는 수의 최대 크기는 10억인데, 배열 크기를 1억 만 설정하셨네요. 

1억보다 큰 소수가 입력으로 들어오면 배열 범위를 넘어서서 오류가 발생합니다.

그렇다고 배열 크기를 10억으로 잡으면, 메모리 초과 오류를 보게 되겠죠

소인수 분해 결과를 저장할 수 있는 다른 자료구조를 생각하셔야 합니다.

wjdwldud4190   3년 전

@bupjae

댓글 정말 감사합니다...말씀해주신 방향으로 다시 생각해 보겟습니다.

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