Codeforces Round #742 (Div. 2)-C. Carrying Conundrum

문제 설명

엘리스는 덧셈을 막 배우는 중이다. 엘리스는 덧셈에서 '올림'이라는 개념을 완전히 이해하지 못해서 원래라면 한 자릿수에서 덧셈의 결과가 10이 넘어가면 다음 한자릿수 왼쪽으로 넘어가야하지만 엘리스는 두자릿수 왼쪽으로 넘어가는 덧셈 연산을 했다.

예를 들어 일반적으로 $2039 + 2976$ 을 계산하면 $5015$ 이지만 엘리스는 $15005$ 가 나온다.

자세히 설명하자면 엘리스는 다음과 같은 과정으로 덧셈을 한다.

• $9$ 와 $6$ 을 더해서 $15$ 라는 결과를 도출한다. 그리고 $1$ 을 왼쪽으로 2열 이동해서 올린다. ($0,9$ 라고 써있는 열)
• $3$ 와 $7$ 을 더해서 $10$ 라는 결과를 도출한다. 그리고 $1$ 을 왼쪽으로 2열 이동해서 올린다. ($2,2$ 라고 써있는 열)
• $1$ 와 $0$ 그리고 $9$ 를 더해서 $10$ 라는 결과를 도출한다. 그리고 $1$ 을 왼쪽으로 2열 이동해서 올린다. ($2 , 2$ 라고 써있는 열의 다음 열)
• $1$ 와 $2$ 그리고 $2$를 더해서 $5$ 라는 결과를 도출한다.
• $1$을 더해서 $1$ 라는 결과를 도출한다.

따라서 엘리스는 $15005$ 라는 틀린 답을 도출한다.
엘리스는 밥에게 두 수를 더했고, $n$ 이라는 결과를 도출했다고 말한다. 그러나 밥은 엘리스가 지멋대로 더했다는 사실을 알고 있다. 우리는 밥을 도와서 엘리스가 더한 두 수의 가능한 모든 조합의 수를 구해야한다. 단. $a \neq b$ 인 경우 $(a, b)와 (b, a)$는 다른 조합으로 취급한다.

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

각 테스트케이스는 엘리스가 밥에게 보여준 정수 $n (2 \le n \le 10^9) $ 이 주어진다.

Output
각 테스트 케이스마다 엘리스의 방식대로 덧셈을 할때, $a + b = n$의 식을 만족하는 모든 양의 정수 $(a, b)$ 쌍을 구한다.

Example
input
5
100
12
8
2021
10000

output
9
4
7
44
99

문제 접근

사용한 알고리즘: 조합론, 구현
걸린 시간 : 00:17
아이디어 하나만 떠오르면 풀수 있는 전형적인 ad-hoc문제이다. 이런 문제를 잘 푸려면 결국 코드포스를 많이 풀어봐야 겠지...
문제에서 하는 덧셈은 2자릿수를 올려서 한다. 그렇다면 뒤에서 첫번째 자릿수에서 하는 덧셈은 뒤에서 2번째 자릿수에서 하는 덧셈에 아무 영향을 주지 않는다. 마찬가지로 뒤에서 2번째 자릿수에서 하는 덧셈은 뒤에서 첫번째, 뒤에서 세번째 자릿수에서 하는 덧셈에 아무 영향을 주지 않는다.

따라서 각 숫자의 자릿수를 홀수자릿수, 짝수 자릿수로 나눠서 생각을 하면 쉽게 풀 수 있다. 문제에서 나오는 예시는 $2039 + 2976$ 을 통해서 설명을 해보자. 자릿수를 홀 짝으로 나눠서 생각을 한다고 했으니 $2039$ 를 $23$ 과 $09$ 로, $2976$ 을 $27$ 과 $96$ 으로 나눠서 더해보자.

• $23 + 27 = 50$ (짝수 자릿수)
• $09 + 96 = 105$ (홀수 자릿수)

그리고 이 값을 다시 원상태로 홀 짝 자릿수에 맞게 배열하면 $1$ _ $0$ _ $5$ 사이에 $5$ $0$을 각각 넣으면 $15005$가 된다.

이러면 문제는 다 풀었다. 결국 주어진 $n$을 홀짝 자릿수에 맞게 나눈다음, 각각 나눈수를 만들 수 있는 수 조합을 찾으면 된다. 위에서 설명한 숫자의 경우 두 수를 더해서 50이 되는 조합의 수는 $(0, 50), (1, 49), .... (49, 1), (50, 0)$ 으로 총 51개이다.
두 수를 더해서 105가 되는 조합의 수는 총 106개이다. 여기서 그냥 $51 \times 106$ 를 하면 답이 나온다고 생각 할 수 있는데, 문제가 여기서 함정을 파놓았다.

두 양수의 조합을 구해야 하기 때문에 $a \neq 0, b \neq 0$ 이라는 조건이 추가로 숨겨져있다. 따라서 2를 빼야하고 $51 \times 106 - 2$ 가 최종 답이 된다.

정답 코드

#include <iostream>
#include <string>
using namespace std;

int main(){
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int t; cin >> t;
    while(t--){
        string str; cin >> str;
        string odd, even;
        for(int i = 0; i < str.size(); i++){
            if(i % 2) odd += str[i];
            else even += str[i];
        }
        if(!odd.size()) odd += "0";
        if(!even.size()) even += "0";
        cout << (stoi(odd) + 1) * (stoi(even) + 1) - 2 << "\n";
    }
}