[Java] 백준 20500번: Ezreal 여눈부터 가네 ㅈㅈ - DP(다이나믹 프로그래밍)

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

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

 

 

---

 

문제는 짧았지만, 아이디어를 생각하기가 어려웠다.

N이 1515이하이므로 완전 탐색을 하면 2^N 이 되어, 시간 초과가 날 것이다.

그렇기 때문에 1의 자리수 부터 N의 자리수까지 DP를 통해 구현할 것이다.

 

먼저, 15의 배수의 조건을 알아야 한다.

15는 3과 5의 공배수이므로, 3의 배수 성질과 5의 배수 성질을 가지고 있다.

3의 배수의 성질은 각 자릿수의 합이 3으로 나누어떨어진다.

5의 배수의 성질은 일의 자리가 0 또는 5이다.

 

위 성질을 알고 시작해야 한다.

 

한 자릿수는 15보다 작기 때문에 15의 배수가 될 수가 없어서 이 부분을 따로 처리해 줘야 한다.

if(N == 1){
    System.out.println("0");
    return;
}

 

두 자릿수는 11, 15, 51, 55 가 올 수 있다.

우리는 1과 5로만 구현을 해야 하므로 일의 자릿수는 무조건 5가 되어야 함을 알 수 있다.

1은 이미 5의 배수 성질에 만족하지 않아 15의 배수에 해당하지 않기 때문이다.

 

따라서 15, 55만 해당하는데 15는 15의 배수에 해당하지만, 55는 15의 배수에 해당하지 않는다.

 

하지만, 나중에 세 자릿수, 네 자릿수 ... 등에 1이나 5를 추가하여 3의 배수에 만족했을 경우에는 15의 배수가 될 가능성이 있으므로, 이 부분을 고려하여 계산해줘야 한다.

 

예를 들어, 나머지가 1일 경우(4) +5를 해주면 3의 배수(6)가 되어 15의 배수가 가능해진다.

나머지가 2일 경우(5) +1을 해주면 3의 배수(6)가 되어 15의 배수가 가능해진다.

 

세 자릿수의 합에서 3으로 나눈 나머지가 0인 경우 =

두 자릿수의 합에서 3으로 나눈 나머지가 1인 경우 + 두 자릿수의 합에서 3으로 나눈 나머지가 2인 경우

즉, dp[i][j]은 j 자릿수에서 3으로 나눴을 때의 나머지 i의 개수라고 할 때, dp[0][3] = dp[1][2] + dp[2][2] 라고 할 수 있을 것이다.

 

이것을 일반화한다면, dp[0][i] = dp[1][i-1] + dp[2][i-1] 이다.

또한, dp[1][i] = dp[0][i-1] + dp[2][i-1] 이 될 수 있다. (나머지 0 +1 = 1, 나머지 2 +5 = 7 이므로 나머지가 1이 된다.)

마찬가지로, dp[2][i] = dp[0][i-1] + dp[1][i-1] 도 된다.

 

그리고, 수가 커지는 것을 방지하기 위해 MOD 연산을 해준다.

dp[0][i] = (dp[1][i-1] + dp[2][i-1]) % MOD;
dp[1][i] = (dp[0][i-1] + dp[2][i-1]) % MOD;
dp[2][i] = (dp[0][i-1] + dp[1][i-1]) % MOD;

 

 

소스 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		long MOD = 1000000007L;
		int N = Integer.parseInt(br.readLine());

		if(N == 1){
			System.out.println("0");
			return;
		}

		long[][] dp = new long[3][N+1];
		dp[0][2] = dp[1][2] = 1;

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

		System.out.println(dp[0][N]);
	}
}