오랜만에 돌아왔다. 계속 논 건 아니다...
재귀 관련 알고리즘에 약한 거 같아서 재귀 공부하다가 멘탈 터졌었다...
그래서 이틀 빡세게 쉬고 다시 맘 잡고 하는 중이다.
오늘은 접근하는 시도는 좋았으나 결국 내 힘으로 풀지 못한 문제를 가져왔다.
문제링크
https://www.acmicpc.net/problem/20500
설명
1과 5로만 이루어진 수들 중 15의 배수가 몇 개인지를 구하는 문제이다.
1부터 1515까지의 자릿수가 주어진다.
문제의 시간제한, 메모리 제한, 주어지는 N의 제한까지 극한의 컨셉으로 1515를 맞춘 게 재미있다ㅋㅋㅋ
근데 이즈리얼 여눈부터 가는 거도 좋지 않나??^^
일단 어떤 수가 15의 배수임을 만족하려면 끝자리가 0이나 5이어야 한다.
위 문제에서는 모든 수가 1 또는 5로만 이루어져야하므로, 끝자리가 5이어야 함을 알 수 있다.
그리고 모든 15의 배수는 모든 자리의 수의 합이 3의 배수이다.
그러므로 우리는 모든 자리의 수의 합이 3의 배수이며, 끝자리가 5인 숫자의 개수를 구해야 함을 알 수 있다.
먼저 시도한 방법은 1부터 N까지의 자릿수의 숫자들을 모두 구해서 15의 배수인지 아닌지를 판별하는 방법이다.
하지만 N의 자릿수의 숫자의 개수가 2^1515이므로 바로 포기하도록 하자.
그 다음으로 시도한 방법이 답을 만족하는 N 자릿수의 개수를 dp[n]라 할 때, 이전 dp[n - 1], dp[n - 2]들을 통해 점화식을 만들 수 있는 지 숫자를 전부 써가면서 확인해보았다.
0 1 1 3 5 11 21 ... 순서로 늘어나는데, 도저히 점화식을 만들 수 없었다.
1시간 정도 계속 시도한 후, 정답을 보았는데 솔직히 못 풀었을 거 같긴 하다...
이 문제의 핵심은 숫자를 써나가면서 나오는 N 자릿수의 모든 숫자를 3으로 나눈 나머지에 따라 나눠 저장해주는 것이다.
자릿수가 하나 늘어가면 그 수의 모든 자리의 수의 합은 1 또는 5가 늘어나게 된다.
dp[0][n - 1]이 5라면, dp[1][n]과 dp[2][n]도 5가 된다는 것이다.
이러한 방식으로 1일 때만 dp를 따로 저장해 준 뒤, n까지 구해나가면 된다.
요즘 dp문제를 풀면서 느끼는 건, 이분 탐색에서 start와 end를 줄여나가기 위해 기준을 먼저 정하는 것이 중요한 것처럼 dp에서도 일차원 배열만으로도 구할 수 있는지, 이차원이라면 다른 한 가지 기준은 무엇으로 잡아야 하는 지, 이 기준을 빨리 찾아내는 것이 중요하다는 것이다.
위 문제에서는 3으로 나눈 나머지가 또 다른 기준이 되었고, 나는 모든 자리의 수의 합이 3의 배수를 만족해야 한다는 것을 바로 찾았지만 나머지 50분 동안 3으로 나눈 나머지를 활용할 생각은 하지 못했다.
틀린 문제도 일주일 정도 이따가 다시 풀어가면서 여러 문제 유형들을 익혀나간다면, 이 기준을 빨리 찾을 수 있을 거라 생각한다.
코드
#include <iostream>
#include <vector>
#define num 1000000007;
using namespace std;
int n;
long long arr[3][1516]; // 3으로 나눈 나머지, 자릿수
void setdp() // 자릿수가 1일 때를 미리 설정
{
arr[0][1] = 0;
arr[1][1] = 0;
arr[2][1] = 1;
}
void solve()
{
cin >> n;
setdp();
for (int i = 2; i <= n; i++)
{
arr[0][i] = (arr[1][i - 1] + arr[2][i - 1]) % num;
arr[1][i] = (arr[0][i - 1] + arr[2][i - 1]) % num;
arr[2][i] = (arr[0][i - 1] + arr[1][i - 1]) % num;
}
cout << arr[0][n];
}
int main(void)
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
solve();
return 0;
} 