2 x n 타일링_복습2

2026.10.09

문제 풀이

나의 코드

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

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

AI 코드

시간 복잡도: $O(n)$
코드 분석

전체적인 구조는 동일하다.
배열 대신 변수를 사용하여 메모리를 아꼈다.

class Solution {
    public int solution(int n) {
        final int MOD = 1000000007;
        if (n <= 2) return n;          // f(1) = 1, f(2) = 2

        int prev = 1, cur = 2;         // f(1), f(2)
        for (int i = 3; i <= n; i++) {
            int next = (prev + cur) % MOD;
            prev = cur;
            cur = next;
        }
        return cur;
    }
}

문제 풀이 후기

해당 문제가 피보나치 수와 같은 규칙을 가지고 있다는 사실을 기억하고 있었다.
정답을 이미 아는 문제나 다름없어서 맞추긴 했지만 맞췄다고 하기 애매하다.
그러나 비슷한 유형의 문제가 출제되었을 때 이를 기억할 수 있을 것이다.