11726 2xn 타일링

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

11726번: 2×n 타일링

 

풀이 : dp[n] = dp[n-1]+dp[n-2]

 

 

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



public class Main {

	 public static int dp []; 
	
	  public static void main(String[] args) throws IOException {

		  BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		  int N = Integer.parseInt(br.readLine()); 
		 dp = new int[1001];
		  
		  for(int i=0;i<1001;i++) {
			  dp[i]=-1;
		  }
		  
		  
		  System.out.println(Tile(N));
		  
	  }
	  
	  public static int Tile(int N) {
		  
		  dp[0]=0;
		  dp[1]=1;
		  dp[2]=2;
		  
		if(dp[N]==-1) {
			  dp[N] =(Tile(N-1) + Tile(N-2))%10007;
		  }
	  
	  return dp[N];
		  
	
		  
	  }}

 

dp 배열을 1001 의 크기만큼 만든 이유는 입력값의 범위가

1이상 1,000이하 이기 때문이다.

 

dp[0]은 실질적으로 사용하지 않고

dp[1]~dp[1,000] 사용한다.

 

 

 

 

 

 

dp 문제를 많이 안 풀어봐서 참고해서 풀었다.

참고 자료 : 

 

https://st-lab.tistory.com/125?category=868019 

[백준] 1904번 : 01타일 - JAVA [자바]