백준 알고리즘 - 퇴사

진짜 퇴사를 앞두고 퇴사 문제를 풀면서 느낌이 조금 달랐다. ㅋㅋㅋㅋ
이 문제도 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);
    }
}

댓글

이 블로그의 인기 게시물

About JVM Warm up

About idempotent

About Kafka Basic

About ZGC

sneak peek jitpack

Spring Boot Actuator readiness, liveness probes on k8s

About Websocket minimize data size and data transfer cost on cloud

About G1 GC

대학생 코딩 과제 대행 java, python, oracle 네 번째