오늘의 키워드
•
DP
•
점화식 구성
•
조건 만족 여부 판단
문제 파악 및 풀이
•
목표는 수 n에 도달하기까지 두 가지 연산 ( +1 또는 +i/2 )를 이용해 최소 횟수를 구하고, 해당 횟수가 제한된 횟수 k 이하인지 판별하는 것이다.
•
즉, 최소 횟수 문제로서 BFS처럼 보일 수 있지만, 이동 방법이 명확히 주어져 있어 DP로 선형 탐색이 가능하다고 판단했다.
•
핵심은 각 수에 도달하기 위한 최소 연산 횟수를 누적하면서, dp[i] 값을 갱신하는 것이다.
최종 풀이 코드
import java.io.*;
import java.util.*;
class Node {
int cur;
int cnt;
public Node(int cur, int cnt) {
this.cur = cur;
this.cnt = cnt;
}
}
class Main {
public static int n, k;
public static boolean isPossible;
public static int[] dp;
public static void main(String[] args) throws IOException {
init();
bfs();
if (isPossible) {
System.out.println("minigimbob");
} else {
System.out.println("water");
}
}
public static void bfs() {
Arrays.fill(dp, 1000001);
dp[0] = 0;
dp[1] = 1;
for (int i = 1; i < n; i++) {
if (i + 1 <= n) {
dp[i + 1] = Math.min(dp[i + 1], dp[i] + 1);
}
if (i + i / 2 <= n) {
dp[i + i / 2] = Math.min(dp[i + i / 2], dp[i] + 1);
}
}
if (dp[n] <= k) {
isPossible = true;
}
}
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());
k = Integer.parseInt(st.nextToken());
dp = new int[n + 1];
}
}
Java
복사
시간 복잡도
•
O(N)
◦
각 수에 대해 +1, +i/2 연산을 적용해보며 갱신하기 때문에, N까지 선형 탐색만 수행함.
오늘의 회고
어려웠던 점
•
처음에는 BFS를 고려했지만, 탐색 공간이 명확히 작고 정해진 규칙을 가진다는 점에서 DP로 바꾸는 게 옳았다.
•
i + i/2 라는 연산 조건이 익숙하지 않아 구현 로직을 실수할 뻔했다.
개선점
•
문제의 조건이 선형 탐색과 누적 갱신으로 해결 가능한지 먼저 판단해보는 연습이 필요하다.
•
+1, +i/2 같은 조건이 있는 경우에도 BFS보다 DP로도 충분히 가능한지 고려하는 시야를 넓히자.