[C/C++] 백준 - 14650번 : 걷다보니 신척역 삼(Small)

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

14650번: 걷다보니 신천역 삼 (Small)

문제

욱제는 ‘삼’이란 음절을 참 좋아한다. 인삼, 홍삼, 해삼, 삼성, 이춘삼(李春森), 삼식이, 삼시세끼, ㄴㄴ 그거 안 삼, 삼과 죽음, 알았삼, 금강삼도 식후경, 걷다보니 신천역 삼, 그리고 특히 일이삼을 좋아한다. 그래서 욱제는 3을 가지고 놀아보기로 했삼.

3개 숫자(0, 1, 2)만 가지고 N자리 3의 배수를 만들어 보삼. 만드는 배수는 자연수 이삼. 0으로 시작하는 수는 만들 수 없는 수 이삼. 3의 배수가 몇 개나 나올 수 있삼?

---

이 문제는 N의 제한이 9라 매우 작다. 백트래킹으로도 충분히 해결이 가능할 것 같지만 DP로 해결하였다. 

3의 배수인지 판정하는 방법은 각 자리의 수 총합이 3의 배수라면 그 수는 3의 배수가 된다.

 

그래서 재귀로 각 자리의 인덱스와 0, 1, 2 세 개의 수 중 하나를 메모이제이션하고 합은 재귀함수의 매개변수로 넘겨주어 판별하였다.

 

#include <algorithm>
#include <iostream>
#include <numeric>
#include <cstring>
#include <string>
#include <vector>
#include <queue>
#include <stack>
#include <cmath>
#include <ctime>
#include <climits>
#include <set>
#include <map> 
#define fastio ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define ll long long	
#define ull unsigned long long
#define INF 987654321
#define Mod 1234567
#define endl '\n'
#define ENDL cout << endl

using namespace std;

int N;
int cache[10][3];

void input() {
	cin >> N;
}

int solve(int index, int number, int sum) {
	if (index == N) {
		if (sum % 3 == 0) return 1;
		return 0;
	}
	int& ret = cache[index][number];
	if (ret != -1) return ret;

	ret = 0;
	for (int i = 0; i < 3; i++) {
		ret += solve(index + 1, i, sum + i);
	}
	return ret;
}

int solution() {
	memset(cache, -1, sizeof(cache));
	return solve(1, 1, 1) + solve(1, 2, 2);
}

int main() {
	fastio;
	input();
	cout << solution() << endl;

	return 0;
}