백준 - 퇴사

 

문제 설명

나는 퇴사 전날 까지 많은 수익을 낼것이다.

하루 마다 벌어들일 수 있는 수익과 처리 기간이 주어진다.

이것들을 잘 분배하여 최대 수익을 낼 것이다.

생각한 아이디어

퇴사 n+1날은 일을 할 수 없으니 n일 까지만 일을 할 수 있다.

dp[i] =: i 날 부터 시작해서 퇴사 전날까지 벌어들일 수 있는 수익으로 맨 뒤부터 데이터를 채워나갔다.

풀이

static class Node {
		private int day;
		private int profit;

		public Node(int day, int profit) {
			this.day = day;
			this.profit = profit;
		}
	}

	public static void main(String[] args) throws IOException {
		BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));

		int n = Integer.parseInt(reader.readLine());
		List<Node> nodes = new ArrayList<>();
		for (int i = 0; i < n; i++) {
			StringTokenizer tokenizer = new StringTokenizer(reader.readLine());
			nodes.add(new Node(
				Integer.parseInt(tokenizer.nextToken()),
				Integer.parseInt(tokenizer.nextToken())
			));
		}

		int answer = solution(n, nodes);

		System.out.println(answer);
	}

/**
	 * note: 주어진 N일 동안 가장 돈을 많이 벌려고 한다.
	 *  - n+1일날은 무조건 퇴사할 거다. =: n일 까지는 일할 수 있다.
	 * @param n : 퇴사날
	 * @param nodes : 처리기간과 수익이 담은 데이터
	 * @return : 최대 수익률
	 */
	static int solution(int n, List<Node> nodes) {
		int dp[] = new int[n + 1];
		int maxValue = 0;

		for (int i = nodes.size() - 1; i >= 0; i--) {
			int endDay = nodes.get(i).day + i;

			if (endDay <= n) {
				dp[i] = Math.max(nodes.get(i).profit + dp[endDay], maxValue);
				maxValue = dp[i];
			} else {
				dp[i] = maxValue;
			}
		}

		return dp[0];
	}