[프로그래머스 level_3] 2 x n 타일링 for JAVA

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

프로그래머스

[문제 설명]

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

• 타일을 가로로 배치 하는 경우
• 타일을 세로로 배치 하는 경우

예를들어서 n이 7인 직사각형은 다음과 같이 채울 수 있습니다.

직사각형의 가로의 길이 n이 매개변수로 주어질 때, 이 직사각형을 채우는 방법의 수를 return 하는 solution 함수를 완성해주세요.

 

제한사항

• 가로의 길이 n은 60,000이하의 자연수 입니다.
• 경우의 수가 많아 질 수 있으므로, 경우의 수를 1,000,000,007으로 나눈 나머지를 return해주세요.

입출력 예

n	result
4	5

입출력 예 설명

입출력 예 #1
다음과 같이 5가지 방법이 있다.

 

[풀이]

처음에는 dfs로 모든 경우에 수를 찾아서 해보려고 했지만 n이 조금만 길면 스택오버플로우가 발생하여서 실패..

뭔가 규칙이 있어 보여서 규칙을 찾으려고 했고 증가하는 수의 규칙이 피보나치 수처럼 증가하는 것을 발견했다.

그래서 DP(dynamic programming)을 재귀로 구현. 재귀로 구현하니 실패. 이유는 찾지 못했다. 그래서 다른 분들의 질문을 보니 최종 반환 값에만 1,000,000,007을 나눠주는 것이 아니라 DP 배열에 수를 넣을 때부터 넣어준다는 것을 알았다.

근데 그렇게 해봐도 실패 ㅠㅜ. 이유를 도저히 못 찾겠어서 그냥 반복문으로 DP를 구현했더니 됐다. 정말 알 수 없다.. 혹시 재귀로 했을 땐 안 되는 풀이가 반복문으로 되는지 아시는 분 있으면 댓글 부탁드립니다 ㅠㅜ.

[코드]

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

느낀 점 : 알고리즘 실력이 조금 느는가 싶더니 또다시 주춤한 것 같다. 이제 재귀에 대한 이해도가 높아져서 재귀를 막 해보려고 하니 따져야 할 것들이 더 생겨서 더 공부를 해야 될 것 같다. level 4까지 화이팅..

 

**피드백은 언제나 환영입니다!!