백준 알고리즘 - 퇴사
진짜 퇴사를 앞두고 퇴사 문제를 풀면서 느낌이 조금 달랐다. ㅋㅋㅋㅋ
이 문제도 DFS로 풀 수 있지만, 다른 사람이 푼 코드를 참고했다.
재귀로 풀었는데 DFS보다 연산의 횟수를 조금이나마 줄일 수 있었다.
하지만 이 문제를 DP로 푸는 사람도 보았는데, 아직까지 DP의 개념은 이해하지만
스스로 문제해결에 구현 하기에는 공부를 더 해야겠다고 생각했다.
import java.util.Scanner;
public class Main {
private static int result = 0;
public static void main(String[] args) {
Scanner scn = new Scanner(System.in);
int N = scn.nextInt();
int[] takenTime = new int[N];
int[] benefits = new int[N];
boolean[] isWork = new boolean[N];
boolean[] visited = new boolean[N];
for (int i = 0; i < N; i++) {
takenTime[i] = scn.nextInt();
benefits[i] = scn.nextInt();
}
scn.close();
goRecursive(0, 0, N, takenTime, benefits);
System.out.println(result);
}
private static void goRecursive(int depth, int benefit, int N, int[] takenTime, int[] benefits) {
if (depth == N) {
result = Math.max(result,benefit);
// System.out.println(result);
return;
}
goRecursive(depth + 1, benefit, N, takenTime, benefits);
if (depth + takenTime[depth] <= N)
goRecursive(depth + takenTime[depth], benefit + benefits[depth], N, takenTime, benefits);
}
}
이 문제도 DFS로 풀 수 있지만, 다른 사람이 푼 코드를 참고했다.
재귀로 풀었는데 DFS보다 연산의 횟수를 조금이나마 줄일 수 있었다.
하지만 이 문제를 DP로 푸는 사람도 보았는데, 아직까지 DP의 개념은 이해하지만
스스로 문제해결에 구현 하기에는 공부를 더 해야겠다고 생각했다.
import java.util.Scanner;
public class Main {
private static int result = 0;
public static void main(String[] args) {
Scanner scn = new Scanner(System.in);
int N = scn.nextInt();
int[] takenTime = new int[N];
int[] benefits = new int[N];
boolean[] isWork = new boolean[N];
boolean[] visited = new boolean[N];
for (int i = 0; i < N; i++) {
takenTime[i] = scn.nextInt();
benefits[i] = scn.nextInt();
}
scn.close();
goRecursive(0, 0, N, takenTime, benefits);
System.out.println(result);
}
private static void goRecursive(int depth, int benefit, int N, int[] takenTime, int[] benefits) {
if (depth == N) {
result = Math.max(result,benefit);
// System.out.println(result);
return;
}
goRecursive(depth + 1, benefit, N, takenTime, benefits);
if (depth + takenTime[depth] <= N)
goRecursive(depth + takenTime[depth], benefit + benefits[depth], N, takenTime, benefits);
}
}
댓글
댓글 쓰기