kch1285   2년 전

안녕하세요 

제 알고리즘은 일단 수를 받고 그 수들중 인접한 수들의 차이를 반복문으로 구합니다 (수가 2개남을때까지)

예를 들어 34 58 106 142가 들어왔을때,

34 58 106 142

24(58-23) 48(106-48) 36(142-106)

24(48-24) 12(48-36) 이런식으로요.

남은 2개의 수의 최대공약수의 약수를 답으로 생각했습니다. 

제 코드중에서 어디 틀린부분이 있을까요.. 아니면 알고리즘 자체가 잘못됬나요 ??

evenharder   2년 전

알고리즘은 얼추 맞습니다만, 다음 경우를 생각해봅시다.

4

1 4 7 10

while문을 거치고 나면 arr[0], arr[1]에는 0이 저장됩니다.  gcd(0,0)을 부르면 0으로 나누기가 실행되니 멈출 수밖에 없습니다.

이는 인접한 수들의 차는 0이 될 수 없지만 이 차들의 차는 0이 될 수 있기에 발생하는 문제입니다.

때문에 while문을 돌릴 필요 없이, 인접한 수들의 차의 최대공약수를 구하면 됩니다.

evenharder   2년 전

추가로, main 함수에 크기 10^7짜리 배열을 집어넣는 건 환경에 따라서 런타임 에러를 일으킬 수 있습니다. 만일에 대비하여 전역 변수로 만드세요.

kch1285   2년 전

답변 감사합니다. 원래는 인접한 수들의 차의 최대공약수를 구하는 알고리즘을 생각했는데, n이 커서 인접한 수들의 차가 많을 경우때문에 while문 돌려서 수를 2개 남기고, 그 2개의 수의 최대공약수를 구해도 된다 생각했습니다. 저기에 arr[0]와 arr[1]의 수가 같을 경우를 if문으로 추가해서 알고리즘을 다시 짜도 될련지요.

evenharder   2년 전

인접한 수들의 차의 최대공약수를 구해야 하는 것이 맞습니다.

a,b,c의 최대공약수는 gcd(a,b)와 c의 최대공약수와 같기 때문에 반복문으로 확인하시면 됩니다.

처음 두 인접한 수들의 차의 최대공약수를 구하고, 그 수와 다른 차의 최대공약수를 구하고, 또 그 수와 다른 차의 최대공약수를 구하는 방식으로요.

그리고 위의 gcd 알고리즘은 a==b이면서 a!=0인 경우를 잘 처리하고 있기에 굳이 if문을 추가할 필요는 없을 듯 합니다.

kch1285   2년 전

감사합니다!

kch1285   2년 전

흐...여전히 런타임에러가뜨네요...

evenharder   2년 전

약수가 100개가 넘어갈 수 있기 때문입니다.

3
24300000
48600000
72900000

의 경우 차이가 24300000인데 이 수는 약수의 개수가 216개이기 때문에 result 배열의 크기를 초과하게 됩니다.

그리고 1에서부터 arr[0]까지 약수를 확인하는 것은 시간 제한이 걸릴 수도 있습니다. 예를 들면

3
111111111
555555555
999999999

같은 경우에서요. x가 n의 약수이면 n/x도 n의 약수임을 이용해보세요. 보다 빠르게 문제를 풀 수 있습니다.

std::vector를 한 번 구글링해보시는 것도 좋을 듯 합니다.



kch1285   2년 전

덕분에 풀었습니다 감사합니다

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