✔문제링크

boj14501. 퇴사

📝문제설명

다음과 같은 상담 일정을 보고 기간내 가장 많은 페이를 받을 수 있는 경우를 찾으면 된다. 위 사진은 기간(N)은 7일이며 T는 상담하는데 걸리는 기간, P는 금액을 의미한다.

💡해결방법

상담을 하는 경우와 안하는 경우로 나눠 완전탐색으로 문제를 풀었다. 이때, 상담을 진행한다면 그만큼 기간을 이동하여 같은 날짜에 2가지 상담을 진행하는 경우를 방지하였다.

👍코드

package com.algorithm01.basic;

import java.util.Scanner;

public class BOJ14501퇴사 {
	
	static class consult{
		public int day, money;

		public consult(int day, int money) {
			super();
			this.day = day;
			this.money = money;
		}

	}
	
	static int N, ANS;
	static consult[] con;
	public static void main(String[] args) {
		
		Scanner sc =new Scanner(System.in);
		N = sc.nextInt();
		con = new consult[N+1];
		
		for(int i=1; i<N+1; i++){
			int day = sc.nextInt();
			int money = sc.nextInt();
			con[i] = new consult(day, money);
		}
		
		DFS(1, 0);
		System.out.println(ANS);
		
	}
	private static void DFS(int L, int sum) {
		// N+1에 도달하며 최대값을 변수에 담는다.
		if(L==N+1) {
			ANS = Math.max(ANS, sum);
			return;
		}
		/*
		* 상담을 진행하는 경우, 날짜를 의미하는 파라미터 L을
		* 상담 기간만큼 증가시켜 같은 날짜에 상담이 여러번 발생하는 것을 방지
		*/
		if(L+con[L].day<=N+1) DFS(L+con[L].day, sum+con[L].money);
		DFS(L+1, sum);
	}

}