프로그래머스 문제풀이/LEVEL 3

[프로그래머스 / Level 3] 2 x n 타일링

지나가던 개발자 2021. 6. 22. 18:19
반응형

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

 

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

가로 길이가 2이고 세로의 길이가 1인 직사각형모양의 타일이 있습니다. 이 직사각형 타일을 이용하여 세로의 길이가 2이고 가로의 길이가 n인 바닥을 가득 채우려고 합니다. 타일을 채울 때는

programmers.co.kr

문제 접근법

  • 2xn의 직사각형이 있을 때 마지막에 1x2 타일이 없다고 가정하면 그 직사각형은 가로길이 n-1까지의 경우의 수 라고 볼 수 있다.
  • 같은 경우로 2x1 짜리 타일이 없으면 가로길이 n-2까지의 경우의 수 라고 볼 수 있다.
  • DP[N](2xn 까지의 경우의 수) = DP[N-1] + DP[N-2]가 성립한다.

아래는 코드입니다.

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <string>
#include <vector>
 
using namespace std;
 
int dp[60001];
 
int solution(int n) {
    int answer = 0;
    
    dp[1= 1;
    dp[2= 2;
    
    for(int i = 3; i <= n; i++)
        dp[i] = (dp[i - 1+ dp[i - 2]) % 1000000007;
    
    answer = dp[n];
    
    return answer;
}
cs
반응형