[백준 C++] 20500번 Ezreal 여눈부터 가네 ㅈㅈ

20500번: Ezreal 여눈부터 가네 ㅈㅈ

문제 요약

문제

욱제는 15라는 수를 굉장히 싫어한다. 그래서 0으로 시작하지 않고 1과 5로만 구성된 $N$자리 양의 정수 중에서, 15의 배수가 몇 개인지 궁금해졌다. 참가자 여러분도 궁금하지요? 안 궁금함? 15ㄱ

사용 알고리즘

다이나믹 프로그래밍

입출력

• 입력: $N$이 주어진다.
• 출력: 문제의 답을 1000000007로 나눈 나머지를 출력한다. ``` 예제1

입력 1515 출력 939178250

## 풀이
15의 배수라는 것은 3의 배수 && 5의 배수라는 것이다. 3의 배수 판별은 각자리수의 합이 3의 배수이면 되고, 5의 배수의 판별은 끝이 0아니면 5이면 된다. 이 문제에서는 1아니면 5이므로 끝을 5로 고정한다. dp는 2차원 배열로 한차원은 N의 값으로 한차원은 3으로 나눈 나머지로 하면 된다. 끝은 5로 고정이고 앞에 1또는 5를 계속 추가하면서 문제를 풀면 된다.

## 어려웠던 점
없음

## 배운 점 / 느낀 점
문제를 풀어보면 1또는 5를 더하면 나머지가 다른 두 개를 더해서 하는건데 그렇게 할바에는 모든 자리수의 합을 구하고 같은 자리의 수를 빼는게 좀더 이쁜 코드를 만들수 있을 것이라고 생각한다.

## 전체 코드
```cpp
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int n;
vector<vector<int>> dp;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);

    cin >> n;
    dp = vector<vector<int>>(n+1, vector<int>(3, 0));

    dp[1][2] = 1;
    for(int i = 2; i <= n; i++){
        dp[i][0] = (dp[i-1][1]+dp[i-1][2])%1000000007;
        dp[i][1] = (dp[i-1][2]+dp[i-1][0])%1000000007;
        dp[i][2] = (dp[i-1][0]+dp[i-1][1])%1000000007;
        
    }
    cout << dp[n][0];

    return 0;
}