leejk9592   2년 전

안녕하세요, 확장 유클리드 알고리즘을 이용해 문제를 풀어보았는데,

정답을 맞추지 못해 질문드리게 되었습니다.


처음에는 시간초과가 나길래 DFS를 사용하는 extendedEuclid

에서 시간이 오래걸리나 했는데, 알고보니


계산 도중에 long long 형 max 값을 넘어가 

overflow가 발생해서 값이 음수로 계산되서 


while( n < 0 || m < 0 )  // 지금은 수정되어 없는 코드
{

   n += dn;  // 양수로 만들기

   m += dm; // 양수로 만들기
}

에서 시간 초과가 난다는 것을 알아냈습니다.


그래서, long double 형으로 처리를 했는데,

아무래도 이 자료형으로도 overflow를 막을 수가 없는지

이제 시간초과가 아닌 틀렸습니다를 보게 되었습니다.


overflow를 막을  방법이 있을지 도움을 구해봅니다...

ntopia   2년 전

흠... 일단 실수 자료형 쓰면 무조건 틀리고요


alpha * n + beta * m = constant  라고 써놓으셨는데

제가 보기엔 (n, m) 이  alpha * x + beta * y = constant  라는 식의 하나의 해인 것 같은데 맞나요?

이제 그 (n, m) 에서 while 로 답에 도달하는 것은 너무 느립니다.


대신 다음의 성질을 이용해야 합니다.

위 식의 한가지 해 (n, m) 을 알고 있다면

다른 나머지 해 (x, y) 들을  정수 r로 파라미터화 할 수 있습니다.

자세한 내용은

https://math.stackexchange.com...

이것을 읽어보시고요


여튼 그렇게 되면 이제 x >= 0, y >= 0  을 만족해야 하므로

정수 r로 파라미터화 한 식을 여기에 갖다 넣으면 결국 정수 r의 범위를 구할 수 있습니다.

우리는 x 중에서도  최소/최대  만 필요하므로 결국 정수 r의 최소/최대 만 알면 되겠죠.

이를 이용하면 한번에 답으로 도달할 수 있습니다.


도움이 되었으면 좋겠네요.


ntopia   2년 전

아 그리고 이제 발견했는데요

a나 b가 0일 경우가 제대로 처리되지 않는 것 같습니다.

leejk9592   2년 전

아 제가 a나 b가 0일때 제대로 되도록

아래처럼 소스를 방금 고쳤는데, 지금도 안되는 경우가 있는지

확인 한 번 해보겠습니다.


감사합니다

leejk9592   2년 전

ntopia님의 도움으로 2달만에 정답을 맞췄습니다.

진심으로 감사드립니다.

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