[Java] 백준 15486 - 퇴사 2

[Java] 백준 15486 - 퇴사 2

문제번호: 15486(퇴사 2)

풀이(java)

n + 1 에 퇴사를 하기 때문에 그 때까지의 수익을 dp를 이용해서 계속 업데이트 해주면 된다.

먼저 n = 7 이라면 index가 1일부터 시작하므로 한개를 더 생성해주고, 또 마지막 n + 1 날에 퇴사를 하기 때문에 한개를 더 생성해준다. 그 후에 처음부터 탐색을 하면서 현재 index에서 필요한 기간만큼 더해준 dp[i + t[i]] 를 지속적으로 업데이트를 하면 되는데 i + t[i] 는 n + 2와 같거나 크게 되면 dp범위를 초과하므로 i + t[i] < n 이라는 조건을 줘야한다.

그 후에, max값을 이용하는데 현재 max값보다 현재 index의 dp값을 비교해주고, 현재 index의 수익을 더해주는데 해당 수익( max + p[i] )이 dp[i + t[i]] 보다 크면 업데이트를 해주면 된다.

package Solve009; import java.io.*; import java.util.*; public class boj_15486 { static BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); static StringTokenizer st; static int[] t; static int[] p; static int[] dp; public static void main(String[] args) throws IOException { int n = Integer.parseInt(br.readLine()); t = new int[n + 2]; p = new int[n + 2]; dp = new int[n + 2]; for (int i = 1; i <= n; i++) { st = new StringTokenizer(br.readLine()); t[i] = Integer.parseInt(st.nextToken()); p[i] = Integer.parseInt(st.nextToken()); } int max = Integer.MIN_VALUE; for (int i = 1; i <= n + 1; i++) { if (max < dp[i]) max = dp[i]; if (i + t[i] < n + 2 && (max + p[i] > dp[i + t[i]])) { dp[i + t[i]] = max + p[i]; } } System.out.println(max); } }

from http://lee-s-k.tistory.com/11 by ccl(A) rewrite - 2021-12-28 03:02:07