오늘의 키워드
•
동적 계획법(DP)
•
점화식
•
모듈러 연산
문제 파악 및 풀이
•
처음에는 현재 최선의 선택이 미래의 최선이 되지 않을 수 있다고 생각해 그리디가 아니라고 판단했다.
•
또, 정렬된 상태나 조건 기반의 구간 탐색이 아니라는 점에서 이분 탐색도 아니라고 생각했다.
•
하지만 문제를 보고도 이전 결과를 활용할 수 있다는 점을 인지하지 못해서 DP 접근을 떠올리지 못했다.
•
구현이나 백트래킹으로 접근하려 했지만, 힌트를 보고 나서야 DP 문제라는 것을 인지했다.
핵심 아이디어
•
dp[i] = dp[i - 1] + dp[i - m]
◦
i초 동안 할 수 있는 경우의 수는 1초(A)를 마지막에 쓰는 경우와 m초(B)를 마지막에 쓰는 경우의 합이다.
•
단, MOD 1,000,000,007로 나눈 값을 저장해야 한다.
최종 풀이 코드
import java.io.*;
import java.util.*;
class Main {
static final int MAX_N = 10000;
static final int TEMP = 1000000007;
static int n, m;
static int[] dp = new int[MAX_N + 1];
public static void main(String[] args) throws IOException {
init();
for (int i = m + 1; i <= n; i++) {
dp[i] = (dp[i - 1] + dp[i - m]) % TEMP;
}
System.out.println(dp[n]);
}
public static void init() throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
n = Integer.parseInt(st.nextToken());
m = Integer.parseInt(st.nextToken());
for (int i = 1; i <= m; i++) {
dp[i] = 1;
}
dp[m]++; // m초 자체만으로도 하나의 경우이기 때문에 +1
}
}
Java
복사
시간 복잡도
•
O(N)
◦
1부터 N까지 dp 배열을 채우기 때문에 시간 복잡도는 O(N)
오늘의 회고
어려웠던 점
•
문제 유형을 명확히 파악하지 못해 초기에 구현, 백트래킹, 그리디 등 여러 접근을 시도했다.
•
이전 결과를 활용할 수 있다는 점을 간과해서 DP 접근을 떠올리지 못한 점이 가장 컸다.
개선점
•
앞으로는 문제를 접할 때, “이전 결과가 현재 계산에 활용될 수 있는가”를 기준으로 DP 가능성을 빠르게 판단하자.
•
조건에 따라 점화식이 어떻게 구성될 수 있는지를 떠올리는 연습을 지속할 필요가 있다.
•
특히 시간 제한이 빡빡하지 않은 경우, 빠르게 가능한 전략을 검토하고 DP 여부를 먼저 고려하는 루틴을 세우자.