0%

[백준/11726] 2×n 타일링

작성일 Edited on In Disqus:

Baekjoon Online Judge - 11726

Review

  • 타일링을 하나하나 그려서 깨달음을 얻은 문제.
  • 전반적인 건 피보나치 수열과 비슷하다.
  • 맨 앞이 1이 될 경우, 2가 될 경우를 전부 계산하면 된다.
  • 점화식은 A[n] = A[n-1] + A[n-2]
  • 금방 풀은 줄 알았는데 자꾸 틀렸다고 하길래 보니까 10007로 나눈 나머지를 출력하지 않아서 그런 거였다. 920을 입력할 경우 답이 음수가 나왔는데(오버플로우) 정답에 나누기를 하지 말고 중간에 더할 때부터 나머지 값을 계산했더니 정답이 나왔다.
  • 다른 사람들이 푼 걸 보니까 for문으로 많이 풀었더라… 나는 피보나치 함수 풀었던 거 재활용하느라 함수를 만들어서 풀었다.

Code (JAVA)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
import java.io.*;

public class Main {
  
  static long[] memo;
  
  public static long tile(int n) {
    if(n == 1) {
      memo[1] = 1;
      return memo[1];
    } else if(n == 2) {
      memo[2] = 2;
      return memo[2];
    } else if(memo[n] != 0) {
      return memo[n] %= 10007;
    } else {
      memo[n] = tile(n - 1) + tile(n - 2);
      return memo[n] %= 10007;
    }
  }
  
  public static void main(String args[]) throws IOException{
    BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
    int input = Integer.parseInt(bf.readLine());
    memo = new long[input + 1];
    System.out.println(tile(input));
  }
}