boj)11726 - 2xn 타일링
2020. 9. 16. 18:12ㆍPS/boj
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
// # 2xn 타일링
public class boj_11726 {
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static int[] dp = new int[1001];
public static void main(String[] args) throws IOException {
int n = Integer.parseInt(br.readLine());
dp[1] = 1; dp[2] = 2;
for (int i = 3; i <= n; i++) {
dp[i] = (dp[i-1] + dp[i-2]) % 10007;
}
System.out.println(dp[n]);
}
}
- dp 문제의 경우 점화식을 생각하는게 중요한데 점화식을 떠올리기가 어렵다 ...
- 경우의 수를 쪼갠다
- 마지막 부분에 블록을 채우는 방법은 세로막대 하나일경우, 가로막대 두개일경우 이렇게 2가지밖에 없다.
- 세로막대 한 개인 경우는 dp[n-1], 가로막대 두 개인 경우는 dp[n-2]
- dp[n] = dp[n-1] + dp[n-2]
'PS > boj' 카테고리의 다른 글
boj)9095 - 1, 2, 3 더하기 (0) | 2020.09.16 |
---|---|
boj)11727 - 2xn 타일링 2 (0) | 2020.09.16 |
boj)1463 - 1로 만들기 (0) | 2020.09.16 |
boj)17103 - 골드바흐 파티션 (0) | 2020.09.16 |
boj)1212 - 8진수 2진수 (0) | 2020.09.16 |