내가 푼 방법은 n = 1부터 5까지 구하고 해당 결과로 점화식을 찾았다.
n = 1 : 1개
n = 2 : 3개
n = 3 : 5개
n = 4 : 11개
따라서 dp[n] = dp[n-1] + dp[n-2]*2 이란 점화식이 나온다.
내가 푼 해결방식은 너무 별로라서 다른 풀이를 찾아봤는데
다음과 같이 n=3일때 사각형 배치 방식은
시작이 n=2 으로 시작하거나
n=1 에 2x1사각형 가로로 두 개 or 2x2사각형 하나가 붙어있는 형태 즉 n=1로 두가지 형태를 만들 수 있게 된다.
따라서 점화식이 dp[n] = dp[n-1] + dp[n-2]*2 이 된다고 한다.
주의할점
여기서 끝내면 n이 약 40만 넘어도 int범위를 넘어서고 90만 넘어도 long범위를 넘어선다
10007로 나눈 나머지를 출력하는 것을 잊지말자.
import java.util.Scanner;
public class B11727 {
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] = 3;
for (int i = 3; i <= N; i++) {
// dp[i] = (dp[i - 1] + (dp[i - 2] * 2)) % 10007;
dp[i] = (dp[i - 1] + 2 * dp[i - 2]) % 10007;
}
System.out.println(dp[N]);
}
}
'연습문제 > JAVA' 카테고리의 다른 글
[백준 java] 10884 - 쉬운 계단 수 (0) | 2022.09.09 |
---|---|
[백준 java] 11057 - 오르막 수 (0) | 2022.09.08 |
[백준 java] 7576 - 토마토 (0) | 2022.09.05 |
[백준 java] 1874 - 스택 수열 (0) | 2022.09.04 |
[백준 java] 10866 - 덱 (0) | 2022.09.04 |