[백준] 20500번 : Ezreal 여눈부터 가네 ㅈㅈ

🔗 문제 링크

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

---

✍️ 문제 풀이

해당 문제는 다이나믹 프로그래밍 문제로, 보조 코드와 실제 제출용 본 코드로 나누어 풀었다.

보조 코드

1의 자리부터 n의 자리까지 1, 5로 만들 수 있는 모든 수를 2차원 배열인 dp에 갱신하는 Bottom-Up 방식을 사용했고, 이 dp에 저장되어있는 n의 자리수 중 15의 배수인 수의 개수만 세어 출력한다.

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

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

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

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

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

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

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

본 코드

각 자리수일 때 가능한 경우의 수를 확인한 뒤, 이를 통해 점화식을 유추해내야 한다. 1의 자리부터 n의 자리까지 1, 5로 만들 수 있는 수 중 15의 배수인 수의 개수를 dp에 갱신하는 Bottom-Up 방식을 사용했다.

1) 보조 코드에 n을 입력하여 도출되는 각 자리수에 대한 15의 배수의 개수를 살펴보면

• 1일 때 : 0
• 2일 때 : 1
• 3일 때 : 1
• 4일 때 : 3
• 5일 때 : 5
• 6일 때 : 11
• 7일 때 : 21
• 8일 때 : 43
  ... 와 같이 진행됨을 알 수 있다.

2) 이를 살펴보면 각 자리수 별 가능한 경우의 수는

• i가 짝수 일 때 : dp[i] = (이전 자리수의 dp * 2 + 1)
• i가 홀수 일 때 : dp[i] = (이전 자리수의 dp * 2 - 1)
• 이를 점화식으로 표현하면
  • if (i % 2 == 0) dp[i] = dp[i - 1] * 2 + 1
  • else dp[i] = dp[i - 1] * 2 - 1

---

🖥️ 풀이 코드

보조 코드

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

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

int solution()
{
	// 1 자리 수는 1, 5 만 가능
	dp[1].push_back(1);
	dp[1].push_back(5);

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

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

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

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

본 코드

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

using namespace std;
int n;
int dp[1516];	// dp[n]에는 1, 5로 만들 수 있는 n 자리 수 중 15의 배수의 개수가 저장됨.
const int MOD = 1000000007;

int solution()
{
	dp[1] = 0;
	dp[2] = 1;

	int count = 0;
	for (int i = 3; i <= n; i++)			// i가 홀수 일 때 dp[i] : (이전 자리수의 dp * 2 - 1)					
	{										// i가 짝수 일 때 dp[i] : (이전 자리수의 dp * 2 + 1)
		if (i % 2 == 0)
			dp[i] = (dp[i - 1] * 2 + 1) % MOD;
		else
			dp[i] = (dp[i - 1] * 2 - 1) % MOD;
	}
	return dp[n];
}

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

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