[백준] 11727: 2 * n 타일링2 - Java (DP)
Algorithm/BackJun 2024. 1. 14.
목 차
- 문제
- 접근 방식
- 풀이
문제
접근 방식
DP 문제를 다루는 글에서 항상 언급하지만, 먼저 노가다로 n = 1, 2, 3, 4, 5 정도 까지 그려보거나 계산하고 거기서 점화식을 추출하는 방식으로 한다.
특히 이렇게 점화식을 가져올 수 있는 문제에서는 말이다. 여기서는 어떤 점화식이 있을까?
그래서 그려보았다.
n = 4 까지만 그려보았다. 그림에는 없지만 n = 5 일 때는 21 개 이다.
나는 이 챕터에서 내가 점화식을 추출하게 된 과정을 써보려 한다.
n = 1: 1
n = 2: 3
n = 3: 5
n = 4: 11
n = 5: 21
이제 n = 5 일 때를 가정하여 어떻게 하면 21이 나올 수 있을까 생각해 본다. n 을 처음부터 다 더해보기도 하고 두 개만 더해보기도 하고..
근데 보니까 n = 4 일 때: 11.. 뭔가 dp[ n - 1 ] + 무언가 가 확실해 보인다. 근데 보니까 dp[n - 2] * 2를 하면 10이다 그리고 이 둘을 더하면 21이고, 같은 방식으로 4도 해보자. 5 + 3 * 2 = 11. 이 점화식이 정답일 확률이 90%로 올라갔다.
그리고 이 점화식은 정답이었다.
dP[i] = (dp[i - 2] * 2) + dp[i - 1];
그리고 long 타입을 사용하지 않기 위해서(메모리) 처음부터 10,007 을 나누 값으로 저장을 하였다.
풀이
package src.DP;
import java.io.BufferedReader;
import java.io.InputStreamReader;
public class SetTile_Sec {
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(br.readLine());
int[] dp = new int[N + 3];
dp[1] = 1;
dp[2] = 3;
for(int i = 3; i <= N; i++){
dp[i] = ((dp[i - 2] * 2) + dp[i - 1]) % 10007;
}
System.out.println(dp[N]);
}
}
'Algorithm > BackJun' 카테고리의 다른 글
[백준] 1003: 피보나치 함수 - Java (DP) (0) | 2024.01.16 |
---|---|
[백준] 1912: 연속합 - Java (DP) (0) | 2024.01.15 |
[백준] 2606: 바이러스 - Java (그래프 이론) (0) | 2024.01.11 |
[백준] 2178: 미로 탐색 - Java (그래프 이론) (0) | 2024.01.11 |
[백준] 1932: 정수 삼각형 - Java (DP) (0) | 2024.01.11 |