https://www.acmicpc.net/problem/11726
다이나믹 프로그래밍 문제이며, 이 유형의 문제를 해결하기 위해선 점화식을 잘 세워야 한다.
이 문제에서는 항상 세로의 길이가 2로 고정되어 있으므로, 가로의 길이가 1씩 늘어남에 따른 경우의 수의 증가에 주목하면 된다.
각 경우마다 가능한 타일링의 수를 직접 구하다 보니 규칙이 보였다.
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.Scanner;
public class Main {
static int N;
static int[] D;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
N = sc.nextInt();
D = new int[1001];
D[1] = 1;
D[2] = 2;
for(int i=3; i<=N; i++) {
D[i] = D[i-1] + D[i-2];
D[i] %= 10007;
}
System.out.println(D[N]);
}
}
'Koala - 11기 > 코딩테스트 준비 스터디' 카테고리의 다른 글
[백준/C++] 13301 타일 장식물 (0) | 2023.07.23 |
---|---|
[백준/Python] 1958 LCS 3 (0) | 2023.07.23 |
[C++] 백준 15624번: 피보나치 수 7 (0) | 2023.07.23 |
[백준/Python] 14430번 : 자원 캐기 (0) | 2023.07.23 |
[백준/Python] 2240 자두나무 (0) | 2023.07.21 |