6064번 - 카잉 달력
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 나오는 방식으로 햇습니다.그런데 시간 초과가 나오네요ㅠㅠ
더 좋은 방법이나 어느 부분을 고치면 좋을거 같은지 의견좀 부탁드립니다.
수학적으로 접근하는 것을 추천드려요.
확장 유클리드 알고리즘으로 multiplicative inverse 구하면 시간초과 없이 풀 수 있습니다!
댓글을 작성하려면 로그인해야 합니다.
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 나오는 방식으로 햇습니다.
그런데 시간 초과가 나오네요ㅠㅠ
더 좋은 방법이나 어느 부분을 고치면 좋을거 같은지 의견좀 부탁드립니다.