[백준 알고리즘, 다이나믹 프로그래밍] 삼성 코딩 테스트 문제 기출 :: 14501번 퇴사 자바 풀이

안녕하세요 호호만두에요

이번에 풀어볼 문제는 삼성 코테 문제인 14501번 문제에요

이는 백준 온라인 저지에서 풀어볼 수 있어요!!!
https://www.acmicpc.net/problem/14501

14501번: 퇴사

 

이 문제는 다른 시뮬레이션 문제들 보다는 금방 풀었어요

난이도가 그렇게 높지도 않아서 풀만해요

저는 푸는데 정확히 재지는 않았지만 2시간 조금 넘게 걸린것 같아요

휴... 정말 귀신 처럼 빨리 풀기는 너무 힘든것 같아요

 

<문제 초 간단 요점정리>

1. N+1일쨰 되는날 퇴사를 한다

2. 하루에 하나씩 상담을 잡아서 스케줄이 있다.

3. 상담 하나를 하고 있으면 다른 상담을 동시에 진행하지 못한다.

 

<문제 풀이 설명>

우선 끝 쪽에 즉, 퇴사 직전에 있는 상담 업무는 상담을 아얘 할 수 없는 경우이므로

계산에서 먼저 제외를 해주었어요

예를 들어 7일까지 근무하는데 5일 차에 4일이 걸리는 근무가 있다면

이는 업무를 끝까지 할 수 없으니까 제외해줘야 겠죠???

이 부분을 입력을 받으면서 N-i+1 >=day 조건으로 걸러주었어요

 

그 다음 comb함수를 통해서 가능한 경우를 모두 탐색해보았어요

이때 모두라는게 모든 경우의 수는 아니고 조건을 걸어주어서 최적화를 했어요

조합은 1개씩 뽑아보고, 2개씩 뽑아보고.. 최대 스케줄의 크기까지 뽑으면서 계산했어요

 

1. 1개씩 뽑는 경우

1일차만 하는 경우, 2일차만 하는 경우, ..... N일차만 하는 경우

 

2. 2개씩 뽑는 경우

1,2일차만 하는 경우 / 1,3일차만 하는 경우 / 1,4일차만 하는 경우 / ... N-1, N일차만 하는 경우

나머지 3개씩, N개씩 뽑는 경우도 위 처럼 조합을 찾아서 계산해 나갔어요

아 물론 1,2일차를 하는 경우라고는 했지만 1일차 업무를 하면 2일차 업무를 할 수 없기에

이런 경우는 if( current <= consult.i ) 조건을 통해서 걸러주었어요!!

만약 첫 날 업무를 해서 current가 3이라면(0일차로 계산해서) 2일차 업무(consult.i)는 할 수 없겠죠??

 

최대 스케줄크기 까지 하는 것은 모든 업무가 하루만에 끝날 수 있는 경우도 있으니까요!!

이떄 Consult라는 객체를 담는 arrayList를 이용해서 계산했어요

Consult객체에서 i는 업무 번호-1, day는 상담하는데 걸리는 일 수, money는 상담으로 받는 금액이에요

조합을 구하는 과정에서 rr이라는 변수를 통해서 더욱 빨리 검사를 하도록 했어요

그렇게 최대 금액 보다 큰 경우만 maxMoney를 업데이트해주어서

최대 금액을 계산해냈답니다!!!

이해가 안되셨다면 댓글로 남겨주세요

 

 

이게 다이나믹 프로그래밍 문제라는데 뭘 어떻게 쓰는게 DP인지는 잘 모르겠어요

제가 푼게 DP방식으로 푼건지?? 뭐 풀었으면 됐죠 ㅎㅎㅎ

14501번 퇴사 문제의 풀이는 아래 자바 코드가 있으니 참고하시고

깃허브(github)에도 올려놓았으니 참고하실분은 참고하세요!!

도움이 되셨다면 하트 버튼 눌러주시면 감사하겠습니다

https://github.com/wlgh325/BOJ_answer/tree/master/14501(Leave%20the%20Company)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;

class Consult{
	int i;
	int day;
	int money;

	Consult(int i, int day, int money){
		this.i = i;
		this.day = day;
		this.money = money;
	}
}

class Main {
	static int maxMoney = 0;
	static int N;
	static ArrayList<Consult> schedule;
	static int current=0;
	static int rr;

	// N+1일째 되는날 퇴사
	// 하루에 하나씩 상담을 잡음
	// 상담 하나를 하고 있으면 잡힌 다른 상담은 못함

	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		boolean[] visited;
		String input = br.readLine();
		N = Integer.parseInt(input);

		schedule = new ArrayList<>();

		for(int i=1; i<=N; i++){
			String input2 = br.readLine();
			String[] temp = input2.split(" ");
			
			int day = Integer.parseInt(temp[0]);
			int money = Integer.parseInt(temp[1]);

			// 퇴사 직전에 있는 상담 업무중 아얘 할 수 없는 것 제외
			if(N-i+1>=day)
				schedule.add(new Consult(i, day, money));			
		}

		visited = new boolean[schedule.size()];
		
		int scheduleSize = schedule.size();
		for(int i=1; i<=scheduleSize; i++){
			rr = i;
			comb(visited, 0, scheduleSize, i);
		}
		
		System.out.println(maxMoney);
	}

	static void comb(boolean[] visited, int start, int n, int r){
		if(r==0){
			solve(visited, n);
		}
		else{
			for(int i=start; i<n; i++){
				visited[i] = true;
				comb(visited, i+1, n, r-1);
				visited[i] = false;
			}
		}
	}

	static void solve(boolean[] visited, int n){
		int money = 0;
		int temp = 0;

		for(int i=0; i<n; i++){
			if(visited[i]){
				Consult consult = schedule.get(i);
				if(current <= consult.i){
					current = consult.i + consult.day;
					money += consult.money;
					temp++;
				}
				else
					break;
			}
			if(temp == rr)
				break;
		}

		if(temp == rr){
			if(maxMoney < money){
				maxMoney = money;
			}
		}
		current = 0;
	}

}