재귀

문제https://www.acmicpc.net/problem/1629풀이그냥 단순하게 풀면 BufferOverflow 및 시간 초과가 발생하므로 분할 정복을 활용해야 하며, 지수 법칙과 모듈러 방식을 사용하여 진행해야 한다. 지수 법칙은 a^(n+m) = a^n * a^m으로 이를 활용하여 지수가 짝수인 경우와 홀수인 경우의 전개를 보면 아래와 같다.이를 트리 구조로 표현해 보면 아래와 같이 되는 것을 확인할 수 있다.여기까지만 간단하게 코드를 작성해보면 아래와 같다.public static long pow(long A, long exponent) { // 지수가 1일 경우 A^1 이므로 A % C를 리턴 if (exponent == 1) return A % C; /..

문제https://www.acmicpc.net/problem/1074풀이좌측의 그림은 8x8로 이를 4등분을 하면 우측의 그림이 된다. (row, column)의 좌표까지의 칸수를 계산하는 건데, 한 변은 2^N으로 정의한다. 예를 들어 r=4, c=3,N=3 일 때, 일단 한 변의 길이는 8이 되므로 cut(8, 4, 3)가 실행된다. half는 4등분을 했을 때, 4등분 한 사각형의 한 변의 길이이다. 첫 번째로 쪼개졌기 때문에 한 변의 길이인 half = 4가 된다.1 사분면의 시작 값인 0의 좌표 = (0, 0)2 사분면의 시작 값인 16의 좌표 = (0, half)3 사분면의 시작 값인 32의 좌표 = (half, 0)4 사분면의 시작 값인 48의 좌표 = (half, half)구하려는 좌표가 ..