[백준/C++] 14651번: 걷다보니 신천역 삼 (Large)

문제

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

14651번: 걷다보니 신천역 삼 (Large)

---

문제 요약

상신은 '삼'이란 음절을 참 좋아한다. 인삼, 홍삼, 해삼, 삼성, 이춘삼, 삼식이, 삼시세끼, ㄴㄴ 그거 안삼, 삼과 죽음, 알았삼, 걷다보니 신천역 삼, 그리고 특히 일이삼을 좋아한다. 그래서 상신은 3을 가지고 놀아보기로 했삼.

 

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

 

N을 입력 받고 0, 1, 2만 가지고 만들 수 있는 3의 배수의 개수를 출력하삼.+ 숫자가 너무 커질 수 있으므로 1,000,000,009로 나눈 나머지를 출력하삼.

---

코드

#include<iostream>

using namespace std;

int n;

int main() {
	cin >> n;

	if (n == 1) cout << 0;
	else if (n == 2) cout << 2;
	else {
		long long res = 2;
		for (int i = 2; i < n; i++) {
			res *= 3;
			res = res % 1000000009;
		}
		cout << res;
	}

	return 0;
}

---

풀이

결과 먼저 말하자면, 

 

n = 1일 경우 0, n = 2일 경우 2, 나머지 경우에는 2 × 3^(n - 2) 가 답이 된다.

 

3의 배수는 각 자리의 숫자 합이 3의 배수인지 확인함으로 판별할 수 있다.

 

모든 수는 각 자리 숫자 합을 3으로 나눈 나머지가 0, 1, 2인 경우의 수로 나뉜다.

 

n이 3 이상인 n 자리 모든 수 중 3의 배수인 수를 구하기 위해서는 n - 1 자리 모든 수에 대해 10을 곱하고, 3의 배수가 되도록 1의 자리를 맞추어 주면 된다.

 

즉, n자리 숫자의 모든 수 중 3의 배수인 수의 개수는 n-1자리 숫자의 모든 수의 개수와 같다.

 

n - 1자리 모든 수의 개수는 맨 앞자리에 0이 들어갈 수 없으므로 2 ×, 남은 n - 2개의 수에 0, 1, 2 총 3가지가 올 수 있으므로 2 × 3^(n - 2)개이다.

 

+ 여자친구가 더 빨리 품..ㅠㅠ