반응형
SMALL
문제
https://www.acmicpc.net/problem/11726
문제풀이
전형적인 DP 문제이다. 이 문제는 처음에 봤을 때 완전 탐색으로 풀어야하나? 이렇게 고민되기도 하지만, 그렇게 된다면 구현 자체도 복잡할뿐만 아니라 2의 N승까지의 복잡도를 갖기 때문에 시간내에 풀 수 없게된다. 천천히 생각해보면 N = 1, N = 2, N = 3, ... 일때의 상황을 그려보고 점화식으로 풀이가 가능한 형식임을 눈치채야한다.
점화식은 dp[N] = dp[N-1] + dp [N-2] 이다.
dp[1] = 1 // N == 1 일 때 가능한 조합은 1가지 뿐이다.
dp[2] = 2 // N == 2 일 때 가능한 조합은 2가지 이다. (2x1 을 2개 쌓거나, 1x2를 2개 쌓거나)
dp[3] = 3 // N == 3 일 때 가능한 조합은 3가지 이다. (2x1 을 3개 쌓거나, 1x2 1개, 2x1 2개를 위치를 바꿔 놓는 방법 2가지)
dp[4] = 5 // N == 4 일 때 가능한 조합은 5가지 이다.
.
.
.
여기서, 보면 알겠지만 dp[4] = dp[3] + dp[2] = 3 + 2 = 5
dp[3] = dp[2] + dp[1] = 2 + 1 = 3
dp[2] = dp[1] + dp[0] = 1 + 1 = 2 ( N = 0 인 경우는 아무것도 없는 상태 한가지이므로 1로 초기화)
이므로 점화식을 알 수 있다. 이와 같은 방법으로 풀게된다면 매우 쉽게 풀 수 있음을 알 수 있다.
소스코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Main {
public static int N;
public static final int MAX = 10_007;
public static int[] dp;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
N = Integer.parseInt(br.readLine());
dp = new int[N + 1];
// N == 1
dp[0] = 1;
dp[1] = 1;
System.out.println(solve(N));
}
public static int solve(int n) {
if(dp[n] > 0) return dp[n] % MAX;
dp[n] = (solve(n-1) + solve(n-2))%MAX;
return dp[n];
}
}
반응형
LIST
'문제풀이 > 백준' 카테고리의 다른 글
[백준] 1916번: 최소비용 구하기 (Java/자바) (0) | 2024.07.30 |
---|---|
[백준] 14888번: 연산자 끼워넣기 (Java/자바) (0) | 2024.07.28 |
⭐ [백준] 11053번: 가장 긴 증가하는 부분 수열 (Java/자바) (0) | 2024.07.24 |
[백준] 9663 N-Queen (Java/자바) (2) | 2024.07.23 |
[백준] 2580 스도쿠 (Java/자바) (2) | 2024.07.23 |
댓글