[SWEA/C++] 사탕분배(13736번)

1. 개요

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AX8BB5d6T7gDFARO 

SW Expert Academy

※ 본 문제는 SW Expert 아카데미의 문제이므로 무단으로 복제 X

1-1. 설명

나연이는 A개의 사탕, 다현이는 B개의 사탕을 가지고 있다. 아래와 같은 작업을 K번 반복한다 

 - 둘 중 사탕의 개수가 더 적은 사람을 X, 많은 사람을 Y라 하자. (개수가 같을 시 나연이가 X, 다현이가 Y)

 - X가 P개의 사탕을, Y가 Q개의 사탕을 지니고 있을 때, Y는 X에게  자신의 사탕 P개를 준다. X는 2P개, Y는 Q-P개가 된다.

작업 종료 후 두 사람이 지니고 있는 사탕의 개수는 A',B'라고 할때 min(A',B')의 값은 얼마인가?

1-2. 제한 사항

 - 첫 줄에 테스트 케이스 T가 주어짐

 - 각 테스트 케이스는 하나의 줄로 이루어지며, 세 개의 정수가 공백 하나를 사이를 두고 A, B, K가 주어짐

 - A와 B는 1 이상 10^9이하, K는 1이상 2*10^9이하의 자연수

---

2. 구현

2-1. 풀이

초반에는 최솟값을 구하면서 일정 주기가 반복되면 반복문을 종료하고 그 주기에 맞는 최솟값을 구하는 형식으로 진행했다. 하지만 시간초과가 났으며 식을 새로 구해보자는 방법으로 새롭게 도전했지만, 점화식을 찾기 어려워 제대로 찾지 못했다. 다른 사람들의 조언과 풀이법을 통해 모듈러 연산을 구할 수 있다는 것을 깨닫고, 이를 코드로 구현하였다. 

2-2. 코드

#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;

long long result;
int A, B;
int N;

int divCon(int num);

long long power(long long x, long long K) {
    long long result = 1;
    while (K != 0) {
        if (K & 1) result = (result * x) % (A + B);
        x = (x * x) % (A + B);
        K = (K >> 1);
    }
    return result;
}

int main() {
    int T, K;
    string input;
    cin >> T;
    for (int test_case = 1; test_case <= T; ++test_case) {
        cin >> A >> B >> K;
        result = 0;

        if (K == 1) {
            if (A < B) result = min(2 * A, B - A);
            else result = min(2 * B, A - B);
        }
        else result = divCon(K);

        cout << '#' << test_case << ' ' << result << "\n";

    }
    return 0;
}

int divCon(int K) {
    long long re1 = (power(2, K) * A) % (A + B);
    return re1 < (A+B -re1)? re1 : (A+B-re1);
}