[코딩테스트] 백준(BAEKJOON) - 01타일(Java, 1904번)

안녕하세요~

오늘 풀어본 문제는 간단한 DP문제인 01타일입니다.

 

어떤 트릭이 있나 봤는데 그냥 기본적인 피보나치수열이네요~

그래도 오늘 제힘으로 풀었다는것에대해 기분좋게 이번문제 남겨놓겠습니다.

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

1904번: 01타일

다음은 제가 작성한 코드입니다.

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


public class Main {
		public static void main(String[] args) throws NumberFormatException, IOException {
			Scanner sc=new Scanner(System.in);
			int cnt=sc.nextInt();
			
			int[]dp=new int[cnt+1];
			dp[0]=0;
			dp[1]=1;
			
			if(cnt>1)
			{
				dp[2]=2;
				for(int i=3;i<=cnt;i++)
					dp[i]=(dp[i-1]+dp[i-2])%15746;
			}
			System.out.println(dp[cnt]);
	}

}

 

문제를 읽다보면 00과 1을 이용한 숫자의조합..?

오호~라고생각하실 수도 있지만

 

해당 경우의 수에대해 하나씩 노트에 써내려가다보면 규칙이 보입니다.

이런 규칙을 가지면서 피보나치 수열과 같은 공식을 갖게됩니다.

 

DP문제는 손으로 쓰다보면 얻어걸리는 문제가 몇 있는거같아 좋습니다. :D

오늘 문제는 간단하게 여기서 마무리하겠습니다.

 

다들 좋은밤 되시길 바랍니다.

 

감사합니다~