[20500] Ezreal 여눈부터 가네 ㅈㅈ

www.acmicpc.net/problem/20500

20500번: Ezreal 여눈부터 가네 ㅈㅈ

20500번: Ezreal 여눈부터 가네 ㅈㅈ

문제의 답을 1,000,000,007로 나눈 나머지를 출력한다.

 

처음 백준 코드 리뷰이다. 맨날 한다한다 말만 했는데 이제 진짜로 해야지..

신촌 ICPC 3주차 DP 필수 문제 - Ezreal 여눈부터 가네 ㅈㅈ

 

근데 요즘 Ezreal 여눈부터 가긴 함 ㅋ 쨌든 ㄱㄱ

 

---

문제 : 0으로 시작하지 않고 1과 5로만 구성된 N자리 양의 정수 중에서, 15의 배수가 몇 개인지 구해야 함

입력 : N ( 1<= N <= 1515)

출력 : 문제의 답 % 1,000,000,007

---

 

조합으로도 풀 수 있고, DP로도 풀 수 있는데 DP로 푸는 코드를 올려보도록 하겠다.

우선 문제를 풀기 위해 15의 배수를 판별하는 방법을 알아야 한다.

 

15의 배수 = 3의 배수 * 5의 배수이므로, 이 2가지를 모두 만족하면 15의 배수라고 할 수 있다.

 

   1) 각 자리의 숫자의 합이 3의 배수여야 한다. (3의 배수 조건)

   2) 가장 끝자리의 숫자가 0 또는 5여야 한다. (5의 배수 조건)

 

그렇다면 가장 첫번째로 접근할 수 있는 방법은 위의 조건을 모두 만족하는 값들을 구해서 더하는 건데,

N=3일 때 (즉 3자리 수 일 때) 1과 5로만 구성된 수는 총 2^3 = 8가지이다. 그렇다면, N =100 이면 ?

 

2 ^ 100 = jonna 큰 수이다.

즉, O(2^N)이므로 시간 내에 절대 문제를 해결할 수 없을 거란 소리!

직접 구하는 건 택도 없다. 따라서 시간 복잡도를 줄일 수 있는 방법인 DP를 선택해보도록 하자.

 

#include <algorithm>
#include <iostream>
#include <cmath>
using namespace std;

long long MOD = 1000000007;
long long dp[1516][3];

int main() {
	int n;
	dp[2][0] = 1, dp[2][1] = 1;

	for (int i = 3; i <= 1515; i++) {
		dp[i][0] = (dp[i - 1][1] + dp[i - 1][2]) % MOD;
		dp[i][1] = (dp[i - 1][0] + dp[i - 1][2]) % MOD;
		dp[i][2] = (dp[i - 1][0] + dp[i - 1][1]) % MOD;
	}

	scanf("%d", &n);
	printf("%d\n", dp[n][0]);
}

 

dp[i][j] = i번째 자리일 때 j라는 나머지를 가진 수들의 개수 이다.

 

dp[i][0]  => 15의 배수 = dp[i-1][1] + dp[i-1][2]

(dp[i-1][1]에 해당되는 값에 i번째 자리에 5를 넣는다면 나머지가 0이게 됨. 마찬가지로 dp[i-1][2]에 해당하는 값에 i번째 자리에 1을 넣으면 나머지가 0이게 된다)

 

dp[i][1]  => 나머지 1인 애들 = dp[i-1][0] + dp[i-1][2]

(dp[i-1][0]에 해당하는 값에 i번째 자리에 1을 넣는다면 나머지가 1이라 dp[i][1]이 됨. 마찬가지로 dp[i-1][0]에 해당하는 값에 i번째 자리에 5를 넣는다면 나머지가 2라 dp[i-1][2])

 

dp[i][2]  => 나머지 2인 애들

알아서 해보삼

 

우리가 구하려 하는 값은 1과 5로만 구성된 숫자 중에 15의 배수인 값들이니까 마지막엔 dp[n][0] 출력해주면 된다.

 

이게 하다보면 숫자가 너무 커져서 각 자리수를 구할 때 mod로 나눠줘야됨. 안그러면 overflow 나서 큰 수를 입력했을 때 -값이 출력되므로 조심..! 언제 int를 쓰고 long long을 쓰는지 문제를 풀기 전에 미리 생각해보면 좋을 것이다! 

 

 

이즈리얼 : "많고 많은 개발자들 중에 내가 제일 잘났지 ! "

 

여러분들 열심히 해서 이즈리얼이 됩시다 파이팅. 나는 아직 잘나지 못했으니까 언젠가 빛날 그날까지 !

관심없다구요? 어쩌라구요! ㅃㅃㅇ