muleo   2년 전

/**
* 이 문제는 진짜 하루 종일 뒹가뒹가 하면서 생각한 것 같다.

1. 실패 -> https://www.acmicpc.net/submit/1629/79111746
 * 처음에 문제를 봤을 떄는 a, b ,c 가 일단 int 양수 범위의 끝 까지 될 수 있다고 하길래,
 * a 를 c 로 지속적으로 나눠 가면서 b 면 제곱하면 int 를 오버플로우 하는 일은 없다는 생각을 하고선
 * 가볍게 논리 그대로 구현을 했다. 반복문을 돌면서 a 를 b 번 제곱했다. 하지만 시간 초과였다.

2. 실패 -> https://www.acmicpc.net/submit/1629/79122625
 * 다음에 생각한 것은 나머지라는게 반복될 수 도 있다는 점에서 착안했다.
 * 첫번째 시도와 다르지 않지만 중간에 나머지의 반복이 발견되면 빠르게 중단하게끔 로직을 작성하여 시간을 줄여보려고 했다.
 * 하지만 메모리 초과 그리고 정답 자체가 틀릴 때도 있었다.
 * 그 이유를 지금 생각해 보면 애초에 어떤 수의 나머지의 반복을 찾아내는 것이 어렵고,    
 *         ( 아래는 나머지의 반복을 찾아내는 방법 )
 *         ( 1. 나는 첫번째 나머지가 다음번에 등장하면, 첫번째 부터 다음번 까지를 반복 구간이라 생각했다. )
 *         ( 2. 또 다른 것은 다음번이 그다음번과 동일 할 때 이다. 1 3 3 3 3  같이. )
 * 어떤 수는 애초에 나머지가 반복되지 않을 수도 있다는 것이다. -> 메모리 초과

3. 성공 -> https://www.acmicpc.net/submit/1629/79125075
 * 마지막으로 생각한 것은 절반으로 나누는 것이였다. 이 방법을 떠오르게 된 계기는 직접 손으로 8 4 27 을 구하면서 떠올렸다.
 * 8 4 27의 정답은 19 인데, 64 2 27 의 정답도 19 이고 4096 1 27 의 정답도 19이다.
 * 하고 싶은 애기는 64를 27로 나눈 나머지의 10을 제곱한 100을 27 로 나눠도 나머지는 19라는 것이다.
 * 즉 나머지들의 곱셈도 허용 된다는 것이였다.
 * 그렇기 때문에 (a, b, c) 의 결과를 a^b mod c 라고 했을때,
 * (a, b, c) = (a, b/2, c) * (a, b/2, c) % c
 * (8, 4, 27) = (8, 2, 27) * (8, 2, 27) % 27
 * (8*8*8*8 mod 27) = (8*8 mod 27) * (8*8 mod 27) % 27
 *                  = (64 mod 27) * (64 mod 27) % 27
 * 가 성립한다.
 * 점화식이 완성됬으니 재귀함수를 작성하면 끝이다. b 가 홀수인 경우도 포함해서 점화식을 작성하자.
 * 마지막으로 주의할 것은 중간 과정의 나머지들의 곱셈은 int 를 넘어설 수 있기에 더 큰 범위인 unsigned long 을 사용했다.
*/

다른 게시글의 반례를 참고하면 더 좋을 것 같다.
https://www.acmicpc.net/board/view/118644
https://www.acmicpc.net/board/view/116952

마지막으로 "어 (8*8 mod 27) 부분을 메모이제이션 쓰면 되겠다" 라고 생각할 수 있지만, 해당부분을 쓰는 곳은 (8*8*8*8 mod 27) 함수 밖에 없기 때문에
이미 해당 함수의 지역변수로 저장되어 있고, 해당함수 이외에서 다시 호출되는 곳이 없기에 메모이제이션을 할 필요가 없다. 사실상 이미 지역변수에 메모이제이션되어있다.

ssskid   2년 전

아… 뜻밖에 스포당했… ㅜㅠㅜ

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