[Java] 프로그래머스 - 2 x n 타일링 (2단계)

코딩 테스트 풀이 체크리스트
2시간 내에 풀었는가?	O
본인의 실력으로 풀었는가?	O

 

프로그래머스

 

 

 

 

 

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

 

정확성 테스트

테스트 1 〉	통과 (0.19ms, 69.3MB)
테스트 2 〉	통과 (0.05ms, 72.1MB)
테스트 3 〉	통과 (0.16ms, 72.9MB)
테스트 4 〉	통과 (0.23ms, 78.4MB)
테스트 5 〉	통과 (0.05ms, 77.2MB)
테스트 6 〉	통과 (0.20ms, 73.1MB)
테스트 7 〉	통과 (0.05ms, 72.7MB)
테스트 8 〉	통과 (0.19ms, 74.9MB)
테스트 9 〉	통과 (0.26ms, 72.2MB)
테스트 10 〉	통과 (0.25ms, 70.4MB)
테스트 11 〉	통과 (0.14ms, 77.1MB)
테스트 12 〉	통과 (0.06ms, 73.9MB)
테스트 13 〉	통과 (0.11ms, 77.5MB)
테스트 14 〉	통과 (0.13ms, 78.7MB)

 

효율성 테스트

테스트 1 〉	통과 (0.91ms, 52.3MB)
테스트 2 〉	통과 (1.34ms, 52.3MB)
테스트 3 〉	통과 (0.87ms, 52.2MB)
테스트 4 〉	통과 (0.68ms, 51.8MB)
테스트 5 〉	통과 (1.56ms, 51.7MB)
테스트 6 〉	통과 (1.68ms, 53MB)

 

 

 

 

 

처음에는 코드를 dfs로 작성했는데 정확성 테스트에서부터 시간 초과가 나왔다.

 

class Solution {
    int answer;
    public int solution(int n) {
        answer = 0;
        func(n);
        return answer;
    }
    
    public void func(int size) {
        if (size == 0) {
            answer++;
            return;
        }
        
        if (size - 1 >= 0) func(size-1);
        if (size - 2 >= 0) func(size-2);
    }
}

 

 

 

 

 

그래서 절대 dfs로 작성하면 안되겠구나 생각을 했는데 이를 통해서 알게 된 점은 아래의 표이다

 

가로 길이	방법
1	1
2	2
3	3
4	5
5	8
6	13
7	21
8	34
9	55
...	...

 

 

 

 

 

만약에 가로 길이가 3이면 방법은 길이가 2인 경우와 1인 경우의 방법을 더하는 것이었다.

그래서 동적계획법으로 코드를 짜기 위해 배열을 만들고 그 안에 방법 수를 넣었고,

코드의 내용대로 for문으로 3부터 n번까지 돌렸다.

적어도 이렇게 한다면 n의 최대 길이인 60,000번까지 간다고 해도 반복은 60,000번 밖에 안하는 것이기 때문에

시간 초과도 뜨지 않을 것이라고 확신했다.

 

 

 

 

 

근데 점점 숫자가 커지면 int 범위를 넘어갈 것이기 때문에

i-2와 i-1을 더한 값을 문제에서 나누라고 한 1,000,000,007로 나눈 나머지를 넣는 것으로 계산했다.