[BOJ C++] 백준 32981번: 찐 Even Number

 📚 문제

[BOJ C++] 백준 32981번: 찐 Even Number
https://www.acmicpc.net/problem/32981

 

---

 📝 입력 및 출력

---

 🔎 문제 풀이

• 짝수(0, 2, 4, 6, 8)로만 이루어진 n자리 자연수의 개수를 찾는 문제이다. 가장 큰 자릿수가 0이 되지 않도록 주의하여 구한다.
• $n=1$인 경우, [0, 2, 4, 6, 8]로 0이 추가되므로 5개가 된다.
• $n \geq 2$인 경우, 가장 큰 자릿수에 들어갈 수 있는 수는 4개 (0 불가), 그 뒷 자리수는 모두 5개(0, 2, 4, 6, 8)이므로 $4 \times 5^{n-1}$개이다.
• 모듈러의 곱셈 연산은 분배법칙이 성립한다. 즉,
• (A \ B) mod C = ((A mod C) * (B mod C)) mod C** 가 성립한다.
  오버플로우를 방지하기 위해 중간 과정에서 모듈러 연산도 시행한다.
• 매번 같은 연산을 반복하면 시간초과가 발생하므로 DP(동적계획법)을 사용하여 맨 처음에 한 번만 계산하고, 입력받은 값에 대한 결과만 출력한다.

---

 ⌨️ C++ 코드

#include <bits/stdc++.h>
using namespace std;

int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    vector<long long> v(10000001);
    v[1] = 4; // 두 자리 이상인 경우 첫 번째 자리에는 [2, 4, 6, 8] 4개만 가능.
    for (int i = 2; i < 10000001; i++)
        v[i] = v[i - 1] * 5 % 1000000007; // 오버플로우 방지를 위한 모듈러 연산.

    int q;
    cin >> q;
    for (int i = 0; i < q; i++) {
        long long n;
        cin >> n;
        if (n == 1) v[n]++; // 한 자리 수인 경우 0이 추가됨.
        cout << v[n] << '\n';
    }
}

짝수로만 이루어진 n자리 자연수를 구하는 식을 만들 수 있다면, 코드로 구현하는 것은 어렵지 않은 문제이다.