백준(20500번) - Ezreal 여눈부터 가네 ㅈㅈ(Java) (DP)

DP답게 규칙부터 찾으려고 애썼다. 일단 1과 5로 이뤄진 숫자를 찾아야 하는데 2^N만큼 숫자가 만들어져서 귀찮아서 chatGPT한테 물어봤는데, 1511이 15로 나눠진다나 뭐라나... 아무튼 헛수고하고 5자리까지 직접 구해봤다.

 

 

자릿수	1	2	3	4	5
15의 배수 개수	0	1	1	3	5

이렇게 나왔고 규칙을 찾아보니

dp[i] = (dp[i-2]*2 + dp[i-1])

이런 규칙성이 보였고, 그렇게 코드를 구성해 통과했다.

 

<문제>

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

 

<소스코드>

import java.util.*;
import java.io.*;


public class Main
{

	public static void main (String[] args) throws IOException
	{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int n = Integer.parseInt(br.readLine());
		long[] dp = new long[1516];
		
		dp[1] = 0;
		dp[2] = 1;
		
		for(int i = 3 ; i < 1516 ; i++)
		{
			dp[i] = (dp[i-2]*2 + dp[i-1]) % 1000000007;
		}
		
		System.out.println(dp[n]);
		
	}

}