백준 14501번: 퇴사

문제 설명

• https://www.acmicpc.net/problem/14501
• 조건을 만족하는 상담을 통해 얻을 수 있는 최대 이익을 구하는 문제입니다.
  • Ti 변수를 활용해 조건을 만족하는지 확인합니다.
  • Pi 변수를 활용해 이익을 계산합니다.

접근법

• N의 값이 작아서(최대 15) 이분탐색과 백트래킹이 떠올랐습니다.
• 현재가 i일일 때, i일에 예약된 상담을 퇴사일 이전에 끝낼 수 있다면 해당 상담은 진행이 가능합니다.
  • if(i + Ti(lst.get(i)[0])< N) -> 진행해도됨
  • 진행이 가능할뿐 해당 상담이 반드시 최대이익을 내는 데 포함되는건 아닙니다.
• 진행가능한 상담들의 조합을 만들면서 금액을 구했고, 그때마다 최대금액과의 비교를 통해 최대금액을 구했습니다.
  • answer = Math.max(answer, Sum);

정답

import java.util.*;

public class Main {
	static int N, Sum, answer;
	static List<int[]> lst;
	static boolean[] v;

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		N = sc.nextInt();
		lst = new ArrayList<int[]>();
		for (int i = 0; i < N; i++) {
			int t = sc.nextInt();
			int p = sc.nextInt();
			int[] temp = { t, p };
			lst.add(temp);
		}

		for (int i = 0; i < N; i++) {
			v = new boolean[N];
			Sum = 0;
			BackT(i);
		}
		System.out.println(answer);
	}

	public static void BackT(int start) {
		answer = Math.max(answer, Sum);
		for (int i = start; i < N; i++) {
			if (i + lst.get(i)[0] <= N) { // 종료 조건
				Sum += lst.get(i)[1];
				BackT(i + lst.get(i)[0]);
				Sum -= lst.get(i)[1];
			}

		}
	}

}

기타

• 백트래킹이 원하는대로 잘 설계되지 않았다.
  • 문제를 통과한 후 코드를 다시 확인해 봤는데 백트래킹이 맞는지 모르겠다.
• 인터넷을 검색해보니깐 다른사람들은 dp로 풀었다.
  • 문제를 보고 dp가 적용가능한지 판단하는 능력이 조금 더 필요할 거 같다.