[SWEA] 13736번 사탕 분배 - 분할 정복(java)

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AX8BB5d6T7gDFARO&categoryId=AX8BB5d6T7gDFARO&categoryType=CODE&problemTitle=%EC%82%AC%ED%83%95&orderBy=FIRST_REG_DATETIME&selectCodeLang=ALL&select-1=&pageSize=10&pageIndex=1 

SW Expert Academy

나연이는 A개의 사탕을, 다현이는 B개의 사탕을 갖고 있다. 두 사람은 아래와 같은 작업을 정확히 K번 반복하려고 한다.
- 둘 중 사탕의 개수가 더 적은 사람을 X, 더 많은 사람을 Y라고 하자. 단, 두 사람이 같은 개수의 사탕을 갖고 있다면 나연이가 X, 다현이가 Y이다.
- X가 P개의 사탕을, Y가 Q개의 사탕을 갖고 있을 때, Y는 X에게 자신의 사탕 P개를 준다. 결과적으로 X가 가진 사탕은 2P개, Y가 가진 사탕은 Q-P개가 된다.
작업이 끝나고 난 후, 두 사람이 각각 가지고 있는 사탕의 개수를 A',B'라고 하자. min(A',B')의 값은 얼마일까?
[입력]
첫 번째 줄에 테스트 케이스의 수 T가 주어진다.
각 테스트 케이스는 하나의 줄로 이루어지며, 각 줄에는 세 개의 정수 A,B,K (1≤A,B≤10^9, 1≤K≤2⋅10^9)가 공백 하나를 사이로 두고 주어진다.
[출력]
각 테스트 케이스마다, K번의 반복 작업이 끝나고 난 후, 두 사람이 각각 가지고 있는 사탕의 개수를 A',B'라고 할 때, min(A',B' )의 값을 한 줄에 하나씩 출력한다.

핵심

문제는 매우 간단하다. 하지만 단순하게 구현한다면 시간복잡도때문에 통과할 수 없다.

A,B가 1억까지이고, K또한 2억까지 올라가기때문이다.

분할정복을 사용해야한다.

 

정답 코드

import java.util.*;

class Solution {
    static long division(long n, long sum) {
        if (n == 0) {
            return 1;
        }
        long result = division(n / 2, sum);
        result = (result * result) % sum;
        if (n % 2 == 1) {
            result = (result * 2) % sum;
        }
        return result;
    }

    static long find(long a, long b, long k) {
        long sum = a + b;
        long result = (division(k, sum) * a) % sum;
        return Math.min(result, sum - result);
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int t = sc.nextInt();
        for (int i = 0; i < t; i++) {
            long a = sc.nextLong();
            long b = sc.nextLong();
            long k = sc.nextLong();
            System.out.println("#" + (i + 1) + " " + find(a, b, k));
        }
    }
}

해설

거듭제곱 계산에서 a의 1024제곱을 구할 때 a x a x a x a x a x a .....
의 방법으로 한다면 1024 즉 n번의 시간이 필요하지만
(a^512) * (a^512).... 처럼 a를 512번 곱하고 이 수를 서로 곱해주면 계산이 절반이 줄어드는 방식을 이용하면
X의 n제곱 수를 구하는데 필요한 시간복잡도를 O(log n)으로 줄일 수 있다.

이 문제에서 사탕의 개수 중 하나가 일반항으로 나타내면 k번 분배했을 때 (2^k*A)%C가 나온다. 

전체 사탕의 개수는 A+B=C, 일 때 C로 항상 일정하다.
n번째 단계에서 A개를 가지고 있는 사람이 B개를 갖고 있는 사람보다 더 적다면 2A가 되고
반대의 경우 C-A 개를 빼게 될 테니 2A-C 가 된다.
(2A-C) % C 를 하면 ((2A % C) - (C % C))%C 와 동일하고 C %C 는 0이니까 2A % C와 동일합니다.
이 때 모듈러 연산에 의하면 (2A-C % C) 와 (2A % C)는 동일하다.
이를 두 번 반복하면 ((2A % C)2) % C 가 될텐데 정리하면 ((2A %C) ( 2 % C ))%C를 거쳐서 (2^2 A) % C가 된다.

여기서 일반항을 구할 수 있다.
n번째 항에서 (2^n * A) % C 가 된다.

 

 

배운 점

처음에 단순하게 풀었다가 바로 시간초과가 발생하였다.

함정이 있을 것이라 생각하고 천천히 점화식을 세우니 풀 수 있었다.

분할 정복의 경우 시간복잡도에서 매우 유리하기 때문에 알아 두는 것이 유리하다.