BOJ_1904 : 01타일

👉 문제링크

1904번: 01타일

---

---

🔸 문제 분석 🔸

• 타일을 놓는 경우의 수를 n에 따라 나열하면 1, 2, 3, 5, 8...순으로 피보나치 수열이다.

🔸 코드 🔸

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] dp = new int[n+2];

        dp[1] = 1;
        dp[2] = 2;

        for (int i = 3; i < n+1; i++) {
            dp[i] = (dp[i-1] + dp[i-2]) % 15746;
        }

        System.out.println(dp[n]);
    }
}

🔸 코드 해석 🔸

• 피보나치 수열을 int배열 dp에 저장하고, 값은 15746의 나머지로 계속 계산한다.
  • 수열의 최대값이 15745이고, 값을 더할때 15745*2더라 하더라도 int의 범위를 벗어나지 않음으로 dp는 int형 배열이다.
  • n이 1일때 dp[2]에 값을 넣을 수 있도록 dp의 크기는 n+2이다.

---

🔸 end 🔸

• n의 최대값 1,000,000을 넣었을때 시간이 오래걸리지 않아서 바로 제출했는데 런타임 에러가 났다.
  • dp의 크기를 n+1로 했었는데, n이 1일때 dp[2]에 값을 넣을 수 없었기 때문에 오류가 났었다.
  • 최대값 말고도 최소값도 꼭 넣어보도록 하자...