[BOJ 14651] 걷다보니 신천역 삼 (Large) C++ 풀이

문제 링크

www.acmicpc.net/problem/14651

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

 

걷다보니 신천역 삼 (Large) 

시간 제한 2 초

메모리 제한 256 MB

제출 942

정답 459

맞은 사람 408

비율 49.455%

문제

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

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

입력

N을 입력 받으삼 (1 ≤ N ≤ 33,333)

출력

0, 1, 2만 가지고 만들 수 있는 N자리 3의 배수의 개수를 출력하삼. 숫자가 너무 커질 수 있으니까 답을 1e9+9(1,000,000,009)로 나눈 나머지를 출력하삼.

풀이

앞서 포스팅한 자두 나무, 개근상 문제와 유사한 풀이가 가능한 DP문제였습니다.

 

문제에 앞서, 3의 배수의 특징에 대하여 짚어볼 필요가 있습니다.

3의 배수는 "어떤 수의 각 자리수의 합이 3이면 3의 배수이다." 라는 특징을 가지고 있습니다.

예를 들어, 123은 1+2+3=6, 6은 3의배수이므로 123은 3의 배수입니다.

 

이러한 특징을 이용하여, DP배열을 선언하였습니다.

DP[모든 자리수의 합%3][숫자의 길이] = 가능한 3의 배수 개수

따라서, 0 ≤ i ≤ N 에 대하여  아래와 같이 표현할 수 있습니다.

 

DP[나머지가 0][i번째] = (i-1번째가 나머지0) + (i-1번째가 나머지1) + ( i-1번째가 나머지2)

이유는, i-1번째 수에서, 나머지가 0인수에 0, 나머지가1인수에 2, 나머지가 2인수에 1을 덧붙이면 나머지가 0인수가 됩니다. 따라서 DP배열은

DP[0][i] = 합(dp[0~2][i-1])

DP[1][i] = 합(dp[0~2][i-1])

DP[2][i] = 합(dp[0~2][i-1]) 으로 표현됩니다.

우리는 나머지가 0인 수를 출력해야하므로, DP[0][N]을 문제에서 제시된 1,000,000,009로 나머지 연산을 하여 출력합니다.

 

주의할 점은, dp[0][i]가 3가지 값의 합이므로, 최악의 경우 INT_MAX인 2,147,483,647을 초과할 수 있습니다.

따라서 dp배열을 아래와 같이 long long 타입이나, unsigned int 타입으로 자료형을 선언하는것이 안전합니다.

long long dp[3][33334];

unsigned int dp[3][33334];

 

제가 제출한 코드처럼, dp[0][i-1] + dp[1][i-1]을 먼저 1,000,000,009로 나눈 후, 진행하는 것으로도 오버플로우를 방지할 수 있습니다.

#include <iostream>
#include <algorithm>

using namespace std;

#define MOD 1000000009

int N;
int dp[3][33334];
// dp[모든 자리수의 합 %3][숫자의 길이] = 3의배수 개수

int main()
{
	std::ios::sync_with_stdio(false);
	std::cin.tie(NULL);
	cin >> N;

	dp[0][1] = 0; // 0은 3의 배수 아님
	dp[1][1] = 0; // 1은 3의 배수 아님
	dp[2][1] = 0; // 2는 3의 배수 아님

	dp[0][2] = 2; // 12, 21 가능
	dp[1][2] = 2; // 10, 22 가능
	dp[2][2] = 2; // 11, 20 가능
	// 문제의 조건에서 0으로 시작하는 수는 불가능하다 하였으므로 00, 01, 02는 없습니다.

	for (int i = 3; i <= N; i++)
	{
		//본문에서 설명한 dp 계산입니다.
		dp[0][i] += (dp[0][i - 1] + dp[1][i - 1]) % MOD + dp[2][i - 1];
		dp[1][i] += (dp[0][i - 1] + dp[1][i - 1]) % MOD + dp[2][i - 1];
		dp[2][i] += (dp[0][i - 1] + dp[1][i - 1]) % MOD + dp[2][i - 1];

		for (int j = 0; j < 3; j++)
		{	// 문제의 조건인 1,000,000,009로 나눈 나머지입니다.
			dp[j][i] %= MOD;
		}
	}

	cout << dp[0][N] << '\n';

}

질문과 잘못된 정보 수정 요청은 언제나 환영합니다. 편하게 댓글을 달아주세요.

오늘도 부족한 제 글을 읽어주셔서 감사합니다.