asdjkl15   7년 전

x y가 있으면 x == y가 될때까지 M - N을 더해주는 방식으로 했습니다.

M = 13, N = 11, x = 5, y = 6 이면

(5 + 2) % 13 = 7,  7 != 6

(7 + 2) % 13 = 9,  9 != 6

(9 + 2) % 13 = 11,  11 != 6

(11 + 2) % 13 = 0,  13 != 6 0일 때는 13으로 바꿔줍니다.

(13 + 2) % 13 = 2,  2 != 6

(2 + 2) % 13 = 2,  4 != 6

(4 + 2) % 13 = 2,  4 == 6 반복문 총 7번 돌아서 N * 7 + y == 83 나오는 방식으로 햇습니다.

그런데 시간 초과가 나오네요ㅠㅠ

더 좋은 방법이나 어느 부분을 고치면 좋을거 같은지 의견좀 부탁드립니다.

lego0901   7년 전

수학적으로 접근하는 것을 추천드려요.

확장 유클리드 알고리즘으로 multiplicative inverse 구하면 시간초과 없이 풀 수 있습니다!

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