[백준 14650] 걷다보니 신천역 삼 (Small)

문제 링크 : https://www.acmicpc.net/problem/14650

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

 

 

먼저 특정 수에 대해 3의 배수인지 판별하는 방법을 알아보자.

 

각 자리수의 합이 3의 배수이면 3의 배수이다.

 

270, 999, 531, 8787의 경우를 보면 이 사실이 참임을 알 수 있다.

 

---

 

0, 1, 2를 이용해 구성하는 n자릿수의 경우의 수는 n-1자릿수의 경우에 3을 곱한 값이다.

 

$$F_1 = 2$$

$$F_n = 3*F_{n-1}$$

 

이는 n-1자릿수의 마지막에 0, 1, 2를 덧붙이면 서로 다른 n자릿수가 등장하기 때문이다.

 

n-1 번째까지 서로 다르기 때문에 모든 n-1 번째 수들에 대해 각각 0,1,2를 덧붙여도 중복이 발생하지는 않는다.

 

이를 다르게 생각하면 n자리인 모든 수에 대해 재귀함수로 경우의 수를 탐색할 수 있다는 말이 된다.

 

재귀함수는 자리수가 1일 때부터 n일 때까지 하나씩 자릿수를 증가시키며 탐색한다.

 

---

 

재귀함수가 마지막, n자릿수에 도달했을 때 탐색한 수가 3의 배수인지 판별할 수 있어야한다.

 

이를 위해서 재귀함수가 지금까지 모든 자릿수의 합을 저장하는 인자를 가지도록 설계하였다.

 

만약 이 총합이 3으로 나누어 떨어지면 3의 배수이므로 1을 반환, 아니면 0을 반환하여

 

3의 배수만 탐색한 결과값에 누적되도록 하였다.

 

---

 

이런식으로 재귀함수를 설계하면 최악의 경우 몇번의 연산이 필요할까?

 

n의 최댓값인 9가 입력되는 경우 총 3^9 경우의 수에 대한 확인을 해야된다.

 

이는 19683이므로 시간초과 걱정은 할필요가 없어 보인다.

 

---

 

한자릿수에 0은 올 수 없으므로

 

(마찬가지로 n자리수의 맨 앞에 0은 올 수 없다.)

 

main에서 재귀함수를 호출 할 때는 1과 2에 대해서만 호출해준다.

 

#include <iostream>
#define n_ 2200
using namespace std;

int n;

int solve(int sum, int t) {
	if (t == n)
		return sum % 3 ? 0 : 1;

	int ret = 0;
	ret += solve(sum + 0, t + 1);
	ret += solve(sum + 1, t + 1);
	ret += solve(sum + 2, t + 1);
	return ret;
}

int main(void) {
	cin >> n;

	int res = 0;
	res += solve(1, 1);
	res += solve(2, 1);
	cout << res << endl;

	return 0;
}