프로그래머스 lv2 2xN 타일링

문제 링크

2xN 타일링

풀이

class Solution {
    
   public int solution(int n) {
        return fibo(n);
    }

    // dp
    public static int fibo(int n){
        if(n < 3){
            return n;
        }
        
        int fisrt = 1;
        int second = 2;
        
        int answer = 0;
        for(int i = 3; i <= n; i++){
            answer = (fisrt + second) % 1000000007;
            first = second;
            second = answer;
        }
        
        return answer;
    }
}

해설

• 처음에는 dfs로 풀었다. 모든 경우의 수를 찾으면 되는거라고 생각했으니까. 그러나 시간 초과
• 규칙성을 봤더니 피보나치 수열이라서, 재귀로 풀었다. 그러나 시간 초과.
• 이 문제는 dp로 풀어야했다. 재귀로 피보나치 수열을 하면 시간복잡도가 o(n^2)로 좋지 못하다. 심지어 n의 범위는 60000까지이다.
• 그렇기에 memoization과 비스무리하게 해서 풀었다. 전 변수에 계속 새 합의 결과를 기억하게 했다.
• 그랬더니 성공..

소감

• 이 문제도 역시 규칙성을 찾아내는게 관건이었다.
• 역시 아만보라고..지식을 늘려야한다.