Codeforces Round #734 (Div. 3)-A. Polycarp and Coins

문제 설명

동하는 $n$원을 지불해야한다. 동하는 2가지 동전밖에 가지고 있지 않은데, $1$원짜리 동전과 $2$원짜리 동전이다. 동하는 이 동전을 최대한 비슷하게 지불하고 싶어한다.

따라서 동하는 1원짜리 동전과 2원짜리 동전사이의 개수를 최소화 하는 방향으로 돈을 지불하고 싶다. 1원짜리 동전의 개수를 $c_1$, 2원짜리 동전의 개수를 $c_2$라고 할때, 전체 값은 정확히 $n$원이 되어야 한다. 즉 $(c_1 + 2 \cdot c_2 = n)$ 이 식을 만족해야 한다. 그리고 $c_1$과 $c_2$ 차이의 절대값이 최대한 작게 만들어야 한다. 즉 우리는 반드시 이 식의 값을 최소화 해야 한다. $(|c_1 - c_2|)$

Input
첫번째 줄에는 테스트 케이스의 수 $t (1 \le t \le 10^4)$ 이 주어진다.

각 테스트 케이스의 첫번째 줄에는 동하가 지불해야할 금액인 $n (1 \le n \le 10^9)$이 주어진다.

Output
각 테스트케이스마다 두 정수 $c_1$, $c_2$의 값을 공백을 기준으로 출력한다. 답이 여러가지 있으면 그중에 하나를 출력한다.

Example
input
6
1000
30
1
32
1000000000
5

output
334 333
10 10
1 0
10 11
333333334 333333333
1 2

문제 접근

사용한 알고리즘: 수학
걸린 시간 : 00:02
그냥 조금만 생각하면 쉬운 문제이다. 전형적인 문제.

$c_1$ 과 $c_2$ 의 개수를 최대한 맞추는 것이 목적이기 때문에 이 두값을 $c$로 합쳐서 식을 구하면 그냥 $3c = n$이 된다. 그렇다면 경우의 수는 3가지가 된다.

1. $n;mod;3 = 0$ 이 경우는 그냥 $n / 3$이 답이 된다.
2. $n;mod;3 = 1$ 이 경우는 1이 남기 때문에 $c_1 = \frac{n}{3} + 1$ 이고, $c_2 = \frac{n}{3}$ 이렇게 식을 놓으면 차이가 최소가 된다.
3. $n;mod;3 = 2$ 이 경우는 2가 남기 때문에 $c_1 = \frac{n}{3}$이고, $c_2 = \frac{n}{3} + 1$ 이렇게 식을 놓으면 차이가 최소가 된다.

정답 코드

#include <iostream>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int t; cin >> t;
    while(t--){
        int n; cin >> n;
        if(n % 3 == 0) cout << n / 3 << " " << n / 3;
        else if(n % 3 == 1) cout << n / 3 + 1 << " " << n / 3;
        else cout << n / 3 << " " << n / 3 + 1;
        cout << "\n";
    }
    return 0;
}