취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 13231번 문제인 Lucky Tickets이다.
문제는 아래 링크를 확인하자.

https://www.acmicpc.net/problem/13231 

이 문제는 2N자리수의 자연수 중 앞 N자리 수의 합과 뒤 N자리 수의 합이 같은 수의 개수를 구하는 문제이다.

이 경우의 수는 합이 각각 0~(9N)인 수들의 개수를 각각 제곱해서 더한 것과 같다는 것을 알 수 있다.

이를 dp를 이용하여 계산해주자.

아래는 제출한 소스코드이다.

#include <iostream>
using namespace std;
typedef long long ll;

ll ans[501];
ll dp[5001][501];

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    for (int i = 0; i < 10; i++) dp[i][1] = 1;
    ans[1] = 10;

    for (int k = 2; k <= 500; k++) {
        int R = k * 10;
        for (int j = 0; j < 10; j++) {
            for (int i = j; i < R; i++) {
                dp[i][k] += dp[i - j][k - 1];
            }
        }
        for (int i = 0; i < R; i++) {
            dp[i][k] %= 1000000007;
            ans[k] += dp[i][k] * dp[i][k];
            ans[k] %= 1000000007;
        }
    }

    int T; cin >> T;
    for (int t = 1;t <= T;t++) {
        int x; cin >> x;
        cout << "Case #" << t << ": " << ans[x] << '\n';
    }
}