2 x n 타일링_복습

2026.09.16

문제 풀이

1차 실행 오류

---

0.0/0.0

시간 초과 오류

---

시간 초과 오류 원인 분석

n < 60000의 범위를 갖는 n값에 대해 재귀를 사용한 것이 원인이다.
코드를 다른 방식으로 다시 작성해야 한다.

---

class Solution {
    private int answer = 0;
    public int solution(int n) {
        dfs(0, n);

        return answer;
    }
    private void dfs(int line, int n) {
        // 세로 배치
        if (line > n) {
            return;
        } else if (line == n) {
            answer++;
            
            return;
        }
        dfs(line + 1, n);
        
        // 가로 배치
        if (line > n) {
            return;
        } else if (line == n) {
            answer++;
            
            return;
        }
        dfs(line + 2, n);
    }
}

2차 실행 오류

---

0.0/0.0

시간 초과 오류

---

시간 초과 오류 원인 분석

재귀를 사용한 것이 애초에 원인이다.

---

class Solution {
    public int solution(int n) {

        return fibo(n + 1) % 1000000007;
    }
    private int fibo(int n) {
        if (n <= 2) {
            return 1;
        }
        return fibo(n - 2) + fibo(n - 1);
    }
}

3차 실행 오류

---

0.0/0.0

실패

---

실패 원인 분석

int 오버플로우가 발생했다.

---

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

나의 코드

---

소요 시간: 1시간 23분
시간 복잡도: $O(n)$

---

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

AI 코드

---

시간 복잡도: $O(n)$

---

코드 분석

나의 코드와 구조는 똑같고, 배열의 사용 유무의 차이가 있다.

---

class Solution {
    public int solution(int n) {
        final int MOD = 1_000_000_007;
        int prev = 1, cur = 1;           // 2×0: 1가지, 2×1: 1가지

        for (int i = 2; i <= n; i++) {
            int next = (prev + cur) % MOD;
            prev = cur;
            cur = next;
        }
        return cur;
    }
}

문제 풀이 후기

문제 조건을 잘 읽어야 한다는 생각이 들었다.
우선 수학적인 규칙이 없다고 판단하고 DFS로 해결하려고 했지만,
결국 시간 초과 오류가 발생하고 말았다.

그리고 피보나치 수열과 같은 규칙성을 띄고 있다는 사실을
내가 직접 알아낸 것이 아닌, 이전에 풀었던 코드가 일부 남아 있어서
"아 맞다 이거 피보나치였지" 하면서 풀 수 있었다.

이런 수학적 규칙을 어떻게 찾아내야 하는지 참 막막하다가도
수학적 규칙만 찾으면 풀리는 문제를 보니 무언가 답답하기도 하고 시원하기도 한
그런 느낌이 든다.