LEVEL 3 : 2 x n 타일링

https://programmers.co.kr/learn/courses/30/lessons/12900

코딩테스트 연습 - 2 x n 타일링

 

• 문제

  • 

    문제

 

---

풀이

• n이 최대 60000까지 인 DP문제이다
  • 예전에 백준에서 한번 풀어본 경험이 있어 금방 해결할 수 있었다
• n = 1 경우의 수 :  1*2 짜리 한개만 올 수 있다
• n = 2 경우의 수 : (1*2 짜리 2개), (2*1 짜리 2개) , 총 2개의 경우의 수
• n = 3 경우의 수 :  (n =1 경우의 수, 2*1 짜리 2개)  , ( n = 2 경우의 수 , 1*2 짜리 한 개) 
• 점화식 = dp[n-2] + dp[n-1]

• public static int solution(int n) {
  	int[] dp = new int[n+1];
      dp[1] = 1;
      dp[2] = 2;
      for(int i=3;i<=n;++i) {
     		dp[i] = (dp[i-2] + dp[i-1])% 1000000007; //(n-2번째 + 2*1 짜리 2개 + n-1번째 + 1*2짜리 1개) 	
      }
  
      return dp[n];
  }