문제
풀이
import java.io.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
int[] arr = new int[1001];
arr[1] = 1; // 2x1 크기의 직사각형을 채우는 방법은 2x1 타일로 채우는 한가지 방법 밖에 없다.
arr[2] = 2; // 2x1 2개로 만들거나 1x2 2개로 만드는 방법이 있다.
for (int i = 3; i <= n; i++) {
// 2 x (n - 1) 크기의 직사각형 뒤에 2x1을 한 개 붙이는 방법 수와
// 2 x (n - 2) 크기의 직사각형 뒤에 1x2를 두 개 붙이는 방법 수의 합으로 구해준다.
arr[i] = (arr[i - 1] + arr[i - 2]) % 10007;
}
System.out.println(arr[n]);
}
}
arr[i] = (arr[i - 1] + arr[i - 2]); 점화식을 그림으로 나타내면 위와 같다. 예를 들어 n이 3일 때는 2x2 직사각형과 2x1 직사각형으로 나누어 생각하고, 각 직사각형을 만들 수 있는 방법의 수를 더하여 구해주면 되는 간단한 로직이다.
'알고리즘(코딩테스트)' 카테고리의 다른 글
백준 1932번 정수 삼각형(JAVA) (0) | 2022.03.01 |
---|---|
백준 9095번 1, 2, 3 더하기(JAVA) (0) | 2022.03.01 |
백준 11062번 카드 게임(JAVA) (0) | 2022.02.28 |
백준 9252번 LCS2(JAVA) (0) | 2022.02.28 |
백준 5582번 공통 부분 문자열(JAVA) (0) | 2022.02.24 |
댓글