[백준] 14650, 14651번 : 걷다보니 신천역 삼 (Small, Large)

🔗 문제 링크

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

---

✍️ 문제 풀이

해당 문제는 다이나믹 프로그래밍 문제로, 1의 자리부터 n의 자리까지 0, 1, 2로 만들 수 있는 모든 수를 2차원 배열인 dp에 갱신하는 Bottom-Up 방식을 사용했고, 이 dp에 저장되어있는 n의 자리수 중 3의 배수인 수의 개수만 세어 답을 도출했다.

1) 0, 1, 2로 만들 수 있는 n의 자릿 수의 개수를 얻고 싶을 때, 해당하는 n을 입력 받는다.

2) 0, 1, 2로 만들 수 있는 모든 수를 저장하기 위한 2차원 배열 dp를 선언한다.

• dp[i]에는 0, 1, 2로 만들 수 있는 i 자리수의 수들이 전부 추가된다.
  (ex. dp[2][0]에는 10, dp[2][1]에는 11, dp[2][2]에는 12 ...)

3) dp[1]에 1과 2를 추가해준다. (1의 자리수는 1과 2만 가능)

4) dp 배열에 0, 1, 2로 만들 수 있는 모든 i 자리수의 수를 갱신한다.

• dp[i]에는 이전 자리수의 모든 숫자들에 10을 곱하고 0, 1, 2를 더한 각각의 수들이 추가된다.
  • dp[2]에 추가되는 수들을 예시로 확인해보면
  • 일단 dp[1]에는 1, 2가 저장되어있다.
  • dp[2]에는 이 1, 2에 각각 10을 곱하고 0, 1, 2를 더해준 수들이 추가된다.
    • 1 * 10 + 0 = 10 / 1 * 10 + 1 = 11 / 1 * 10 + 2 = 12
    • 2 * 10 + 0 = 20 / 2 * 10 + 1 = 21 / 2 * 10 + 2 = 22
  • 이를 점화식으로 표현하면
    • i : 현재 자리수 / j : 이전 자리수에 저장된 수의 인덱스 / k : 0, 1, 2
    • 각각의 j, k에 대해
    • dp[i].push_back(dp[i - 1][j] * 10 + k)

4) dp[n]에 저장되어있는 수들을 모두 3으로 mod 연산하고, 그 중 3의 배수인 수의 개수만 세서 반환하여 출력한다.

---

Small 같은 경우에는 데이터량이 적어 위와 같은 풀이로 풀 수 있었지만, Large는 데이터량이 많아 위와 같은 방식으로 풀면 메모리 초과가 나게 되었다. 따라서 모든 수를 일일이 저장하는 것이 아닌, 각 자리수일 때 가능한 경우의 수를 확인한 뒤, 이를 통해 점화식을 유추해내야 한다.

1) 각 자리수에 대해 가능한 경우의 수를 살펴보면

• 1일 때 : 0
• 2일 때 : 2
• 3일 때 : 6
• 4일 때 : 18
• 5일 때 : 54
  ... 와 같이 진행됨을 알 수 있다.

2) 이를 살펴보면 각 자리수 별 가능한 경우의 수는 이전 자리수에서 가능한 경우의 수 * 3임을 알 수 있다.

• 이를 점화식으로 표현하면
  • dp[i] = dp[i - 1] * 3

---

🖥️ 풀이 코드

Small

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;
int n;
vector<vector<int>> dp(10);	// dp[n]에는 0, 1, 2로 만들 수 있는 모든 n 자리 수가 저장됨.

int solution()
{
	// 1 자리 수는 1, 2 만 가능 (0으로 시작 불가능)
	dp[1].push_back(1);
	dp[1].push_back(2);

	int count = 0;
	for (int i = 2; i <= n; i++)						// i 자리 수는 모든 i-1 자리수에 10 곱하고 (+0, +1, +2) 해준 수들
	{
		for (int j = 0; j < dp[i - 1].size(); j++)
		{
			for(int k = 0; k < 3; k++)
				dp[i].push_back(dp[i - 1][j] * 10 + k);
		}
	}

	for (int j = 0; j < dp[n].size(); j++)				// n자리 수들을 3으로 mod 연산하여 결과가 0일 때만 count 증가
	{
		if (dp[n][j] % 3 == 0)
			count++;
	}

	return count;
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr); cout.tie(nullptr);

	cin >> n;
	cout << solution() << endl;
}

Large

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;
int n;
long long dp[40000];
const int MOD = 1000000009;

int solution()
{
	dp[2] = 2;
	for (int i = 3; i <= n; i++)
		dp[i] = dp[i - 1] * 3 % MOD;

	return dp[n];
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr); cout.tie(nullptr);

	cin >> n;
	cout << solution() << endl;
}