[프로그래머스] 2n 타일링

소스 보러가기
문제 보러가기

---

사용한 알고리즘 및 자료구조

DP , 피보나치

풀이

문제에 대한 접근 방향이 중요하다. 여러 접근에 대한 후보를 떠올리고 최적의 후보를 택하여 접근해보았다. 인덱스 순서대로 접근하려고 했으나, 이내 방향을 바꿔 가장 맨 뒤를 가정하고 접근했다.

내가 N일 때, N-1, N-2에 올 수 있는 모양에 대해서 생각해보면 된다.

• N-1 일 때 : 블록을 세울 수 밖에 없다.

• N-2 일 때 : 세로 블록 2개 , 가로 블록 2개인 경우로 나뉠 수 있다. 하지만 세로 블록 2개인 경우에 N-1인 경우와 같다. 따라서 가로 블록 2개인 경우만 카운팅 된다.

즉, N-1, N-2가 어떠한 블록이 오느냐에 따라서 자동으로 N번째까지 블록이 채워진다.

그러므로 N-1 + N-2 개수를 합하여 더 하면 된다.

N = (N-1)+(N-2) => 피보나치

규칙을 보면 피보나치 수열이 근간이 되어 풀리는 문제다. 자세한건 코드를 보면서 파악하기 바란다.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23

public static int solution(int n) {         int answer = 0;         int s = 1000000007;           int[] dp = new int[n + 1];           dp[0] = 0;         dp[1] = 1;         dp[2] = 2;           for (int idx = 3; idx <= n; idx++) {               dp[idx] = (dp[idx - 2] + dp[idx - 1]) % s;           }           answer = dp[n];           return answer;     }     Colored by Color Scripter

cs

---