프로그래머스 2 x n 타일링

문제 개요

문제 해석

이 문제를 그냥 풀게 되면 시간초과가 뜨게 된다.
-> DP 메모라이제이션을 이용해서 풀어야한다.
이 때 조금 재밌는 부분이 있는데 이를 List로 풀게 되면 효율성 검사에서 시간초과가 발생한다.
이를 해결하기 위해 Capacity를 처음부터 맥스로 만들어 주면 배열처럼 통과하지 않을까? 하는 생각에 선언할때부터 capa를 늘려서 만들었었다.
결과는... 당연히 실패

ArrayList는 배열로 만든 리스트라고 해서 초기 디폴트 값은 10이다. 이를 처음부터 문제에서 주어진만큼 주면 배열이랑 같을 것이라고 판단했었는데 이렇게 풀더라도 시간 초과가 되는 것들이 많았고, 성공한 것들 또한 상당히 많은 시간이 걸렸다.

즉 이문제는 배열을 이용해서 문제를 해결해야한다.

코드

import java.util.*;

class Solution {

    public int solution(int n) {
        int[] memo = new int[n+1];

        //1번지 2번지 추가
        memo[1] = 1;
        memo[2] = 2;

        for(int i = 3 ; i <= n ; i++){
            memo[i] = (memo[i-1] + memo[i-2])%1000000007 ;
        }
        return memo[n];
    }

}

코드를 보면 단순하다.
마치 피보나치수열을 DP로 풀듯 풀었다.

후기

앵간해서는 배열을 이용하는 것이 속도 측면에서 조금 더 빠르다.