solution example.md

프로그래머스 DP 문제

• 2xn 타일링
  • https://programmers.co.kr/learn/courses/30/lessons/12900

문제 이해하기

• 입력값: 가로길이 n
• 가로2 세로1 길이의 타일로 가로n 세로2의 바닥을 가득 채워야 한다.
• 타일 하나는 가로 배치, 세로 배치 두 가지를 할 수 있다.
• 출력값: 만들 수 있는 타일 패턴의 개수

문제 접근 방법

• 가로 길이가 1씩 늘어날때 마다 추가되는 타일의 모양을 직접 손수 그려 확인한다.
• dp[i ]: 가로 길이가 i일때 배치 가능한 바닥의 개수
  • i 바닥 개수는 i-1 바닥의 오른쪽에 1x2 타일을 붙인 개수 d[n-1 ]를 포함한다.
  • 그 외에 새로 추가되는 바닥이 있다. 바닥의 맨 오른쪽 끝 가로2의 부분을 가로2 세로1 타일 두개로 채울 수 있는 것이다.
  • 위 패턴의 개수는 i-2까지 바닥 개수에 하나의 패턴을 추가하므로 d[n-2 ]를 포함한다.
• 제한사항을 제대로 확인해야 한다. 반복문을 수행하며 값이 커질 수 있으니 1,000,000,007으로 나눈 나머지 값을 저장해야 했다.

구현 배경 지식

• 메모라이징 기법 DP

문제를 해결한 코드

class Solution {
    public int solution(int n) {
        int[] dp = new int[n+1];
        dp[0] = 1;
        dp[1] = 1;
        for(int i=2 ; i<=n ; i++){
            dp[i] = (dp[i-1]+dp[i-2])%1000000007;
        }
        return dp[n]%1000000007;
    }
}

못풀었던 이유

• 가로2,세로1 두개가 추가되는 타일이 이전에 저장한 바닥 갯수가 아닌 상수 k개 대로 늘어나는 줄 알았다.
• 하지만 i=6 부터는 그림을 직접 그리는게 부담스러워 졌다.
• 문제에서 주어진 그림은 n=4 이다. n=4 까지 그리면서 패턴을 파악하라. 그 이상은 갈 필요가 없다 는 의도같다.

i를 1씩 늘리며 순서대로 진행할 때 이전 타일에서 안보였던 패턴이 등장했다. 그래서 홀수/짝수로 나누어 풀어보았다. 처음에 나왔던 식은 아래와 같았다. 그리고 테스트 케이스에서 통과하지 못해서 n=5를 그려봤는데 새로운 패턴이 3개나 늘어난걸 확인했다.

if(i%2==0)
    dp[i] = dp[i-1] + dp[i-2];
else
    dp[i] = dp[i-1] + 1;

문제를 해결한 방법

• 새로 늘어나는 타일에 따라 새로 생겨나는 패턴의 규칙을 찾는게 관건이였다.
• 새로운 타일 규칙은 이중for문에서 연산