[문제풀이] 백준 14501 퇴사

import java.util.Scanner; public class 퇴사 { static int N; static int T[]; static int P[]; public static void main(String args[]){ Scanner sc = new Scanner(System.in); N= sc.nextInt(); T=new int[N+1]; P=new int[N+1]; for(int i=1;i<N+1;i++){ T[i]=sc.nextInt(); P[i]=sc.nextInt(); } int result = solution(); System.out.println(result); } /*원리 : dp[] 배열을 만들어 맨 끝날 부터 for문을 돌며 현재 날부터 시작했을 때 얻을 수 있는 최대 비용을 구한다. * 만약 현재 날(i) + 현재날의 상담일수 (T[i]) -1 을 한 값이 N을 넘으면 퇴사 전에 끝낼 수 없는 일이므로 dp[i]=0으로 채워진다. * 현재 날(i) + 현재날의 상담일수(T[i])-1 을 한 값이 N을 넘지 않으면 퇴사 전에 끝낼 수 있는 일이므로 dp[i]=P[i]으로 먼저 셋팅한다. * 그리고 현재날 상담을 끝낸 후, (다음으로 할 수 있는 상담 ~ 다음으로 할 수 있는 상담이 걸리는 날짜)까지의 dp[]값을 확인해 가장 큰 max값을 dp[i]에 더해주면 * 현재 날에 상담할 수 있는 가장 최대 비용을 얻을 수 있다. * * 그리고 최종적으로 (1일차 ~ 1일차 상담이 걸리는 날짜) 까지의 dp[] 값 중 가장 큰 값을 찾으면 N날짜의 기간동안 상담할 수 있는 최대 비용을 얻을 수 있다. */ static int solution(){ int answer=0; int dp[]=new int[N+1]; for(int i=N;i>0; i--){ if(i+T[i]-1>N) dp[i]=0; else{ dp[i]=P[i]; int mday=i+T[i]; if(mday<=N){ int max=dp[mday]; for(int j=mday; j<mday+T[mday];j++){ if(j>N) break; if(max<dp[j]) max=dp[j]; } dp[i]+=max; } } } int mday=1+T[1]-1; for(int i=1;i<=mday;i++){ if(i>N) break; if(answer<dp[i]) answer=dp[i]; } return answer; } }

인터넷 답......

import java.util.Scanner; import java.util.Arrays; public class Main_2 { static final int INF = 10000000; static int N; static int[] T= new int[16]; static int[] P = new int[16]; static int[] dp = new int[16]; public static void main(String args[]){ Scanner sc = new Scanner(System.in); N = sc.nextInt(); for(int i=1; i<=N; i++){ T[i] = sc.nextInt(); P[i] = sc.nextInt(); } Arrays.fill(dp, -1); //먼저 dp를 -1로 초기화 //dp에는 현재 일수에서의 최대 값이 리턴됨 System.out.println(solve(1)); //System.out.println(Arrays.toString(dp)); } static int solve(int x){ if(x==N+1) return 0; if(x>N+1) return -INF; if(dp[x]!=-1) return dp[x]; //dp 값이 구해져 있으면 그것 리턴 return dp[x]=Math.max(solve(x+1), solve(x+T[x]) + P[x]); //dp[x] = x일의 일을 안할 경우, x일의 일을 하고 T[x]일 후의 일을 할 경우 중 최대 값 리턴 } }