14501 - 퇴사(DP)

14501 - 퇴사(DP)

# 주소

https://www.acmicpc.net/problem/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해주어서 최대이익을 구할 수도 있단 걸 알았습니다.

from http://codingrapper.tistory.com/43 by ccl(A) rewrite - 2021-10-04 21:26:56