문제
코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
public class BOJ_14501_DP {
private static int N, answer, size;
private static int[] t,p, sum;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
N = Integer.parseInt(br.readLine());
size = N+5;
t = new int[size];
p = new int[size];
sum = new int[size];
for(int i = 0; i < N ; i++) {
StringTokenizer stk = new StringTokenizer(br.readLine());
t[i] = Integer.parseInt(stk.nextToken());
p[i] = Integer.parseInt(stk.nextToken());
}
for(int i = 0; i < N+1 ; i++) {
sum[i] = Math.max(sum[i], answer);
sum[t[i] + i] = Math.max(sum[t[i]+i], p[i]+sum[i]);
answer = Math.max(answer, sum[i]);
}
System.out.println(answer);
}
}
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
public class BOJ_14501_DFS {
private static int N, answer;
private static int[] t,p;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
N = Integer.parseInt(br.readLine());
t = new int[N];
p = new int[N];
for(int i = 0; i < N ; i++) {
StringTokenizer stk = new StringTokenizer(br.readLine());
t[i] = Integer.parseInt(stk.nextToken());
p[i] = Integer.parseInt(stk.nextToken());
}
dfs(0,0);
}
private static void dfs(int index, int value) {
if(index >= N) {
answer = Math.max(answer, value);
return ;
}
if(index + t[index] <= N) {
dfs(index + t[index], value + p[index]);
}
else {
dfs(index + t[index], value);
}
dfs(index+1, value);
}
}
회고
-
dp라는 방식으로 풀 수 있다고 생각했지만, 오래 걸림
-
DFS로도 풀 수 있다는 것을 블로그 보고 알게 됨
-
문제를 이해하는 데 너무 오래 걸리고, 더 준비를 해야 함
-
바로 코드를 작성하지 말자
-
DFS, BFS 시간 복잡도 : 둘 다 O(N^2)(인접행렬), O(N+E)(인접리스트)