[BOJ - JAVA] 14501 - 퇴사(DP)

# 주소

https://www.acmicpc.net/problem/14501

14501번: 퇴사

 

# 문제

# 문제 해설 및 코드 리뷰

 

import java.util.*;
public class Main{
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        
        int n = scan.nextInt();
        int[][] arr = new int[2][n];
        
        for(int i = 0; i < n; i++) {
            arr[0][i] = scan.nextInt();
            arr[1][i] = scan.nextInt();
        }
        scan.close();
        int dp = 0;
        int count = 0;
        int[] sum = new int[n];
        while(count < n){
            dp = arr[1][count];
        	for(int i = count + arr[0][count]; i < n;){
        		if(i + arr[0][i] > n)
        			break;
        		else {
        			dp += arr[1][i];
        			i += arr[0][i];
        		}
            }
        	sum[count] = dp;
        	count++;
        }
        Arrays.sort(sum);
        System.out.println(sum[n-1]);
    }
    
}

처음에 썼던 코드입니다.

예제 3번가지는 되는데 예제 4번부터 안되요..

이유는 dp문제라서 Math.max를 이용하여 풀이해야하는데, (당장 크기 2짜리 10을 할 수 있지만 크기 2짜리 30 선택하는 것이 최대 이익이므로) 제가 그 부분을 간과하고 풀어서 그렇습니다.

그래서 DP로 풀려면

import java.io.*;
import java.util.*;

public class Main {
	public static int answer = 0;
	public static int n;
	public static int[] arr, ans, dp;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());

        n = Integer.parseInt(st.nextToken());
        arr = new int[n];
        ans = new int[n];
        dp = new int[n];

        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            arr[i] = Integer.parseInt(st.nextToken());
            ans[i] = Integer.parseInt(st.nextToken());
        }

        dfs(0,0);
        System.out.println(answer);

        br.close();
        bw.flush();
        bw.close();
    }
    public static void dfs(int index, int value) {
    	if(index >= n) {
    		answer = Math.max(answer, value);
    		return;
    	}
    	if(index + arr[index] <= n) {
    		dfs(index + arr[index], value + ans[index]);
    	}
    	else
    		dfs(index + arr[index], value);
    	dfs(index + 1, value);
    }
}

이런식으로 작성해야합니다.

문제를 잘 읽어야 풀 수 있습니다. 순서대로 값을 다 넣는것보다 index를 +1시켜줘서 최대 이익을 구할 수도 있기 때문에 dfs(index+1, value)로 answer의 max값을 구해야 합니다.

그것 빼곤 간단한 문제였습니다만, 시간을 너무 잡아먹었네요. 세시간걸렸습니다 ㅋㅋ....

자꾸 예제 4번을 쓰면(10 5 50 4 40 3 30 2 20 1 10 1 10 2 20 3 30 4 40 5 50) 80이 나와서.. 한참을 고민하다가 dfs로 풀되 index를 +1해주어서 최대이익을 구할 수도 있단 걸 알았습니다.