알고리즘 - 퇴사
문제
코드
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());
}
// N+1일 때 퇴사를 하면서 얻을 수 있는 최댓값을 구해야 하므로 N+1까지의 범위를 계산해준다
for(int i = 0; i < N+1 ; i++) {
sum[i] = Math.max(sum[i], answer);
// t[i]번째 이후로 진행할 수 있기 때문에 현재 i에서 t[i]를 더해주어
// 저장된 값을 변경해주어야 한다.
sum[t[i] + i] = Math.max(sum[t[i]+i], p[i]+sum[i]);
answer = Math.max(answer, sum[i]);
}
//System.out.println(Arrays.toString(sum));
System.out.println(answer);
}
}
// DFS를 이용한 방식
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());
}
// n이 작기 때문에 => dfs로도 가능한 듯
// 시작점 => 0번째 인덱스 => value 0으로 설정
dfs(0,0);
}
private static void dfs(int index, int value) {
// TODO Auto-generated method stub
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)(인접리스트)
Author And Source
이 문제에 관하여(알고리즘 - 퇴사), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@39ghwjd/알고리즘-퇴사저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)