[백준] code.plus(브루트포스-재귀,JAVA)14501번, 퇴사

문제 링크

14501번: 퇴사

---

주의사항

• JAVA를 사용하여 프로그램을 사용하였습니다.
• 백준에서 코드를 작성하였을 때 아래 형태에서 Main에서 결과가 출력되어야 합니다.

public class Main{ 	
	public static void main(String[] args){
    }
}

---

문제 설명

---

접근 방법

브루트 포스란.

모든 경우의 수를 대입시켜서 가장 알맞은 경우의 수를 결과로 출력하는 것입니다.

 

이 문제에 핵심은

1. 퇴사 날짜에는 일을 하지 않는다.

2. 하루에 한 가지 상담일만 진행할 수 있다.

3. 최대의 받을 수 있는 금액을 구해야 한다.

 

배열

T : 상담을 완료하는 기간 저장

 

P : 상담했을 때 받을 수 있는 금액 저장

 

 

위에 T, P와 재귀를 통해 최대로 받을 수 있는 금액을 만들었습니다.

 

재귀를 통해 모든 경우의 수에 대한 금액을 비교하여 최대값을 결과로 출력하였습니다.

 

문제에 해결알고리즘은

1. 배열 T와 P를 입력값으로 초기화한다.

2. 재귀를 통해 모든 경우의 수를 구한다.

3. 기간이 퇴근 기간보다 커질 경우 해당 상담은 취소한다.

4. 모든 경우의 수를 비교하여 최대값을 구하고 결과로 출력한다.

 

 

• BufferedReader를 사용하여 입력 값을 저장하였습니다.
• StringTokenizer를 이용하여 T, P 배열을 초기화하였습니다.
• 모든 상담 경우의 수에 금액 최대값을 구하는bestCost 함수를 만들었습니다.
• BufferedWriter에 모든 상담 경우의 수에서 금액의 최대값을 저장하였습니다.
• BufferedWriter에 저장된 결과값을 출력하였습니다.

• bestCost는 재귀를 사용하여 상담의 모든 경우의 수를 구해서 금액의 최대값을 구하였습니다.

 

결과 코드

import java.io.*;
import java.util.*;
public class Main{
	public static int[] T;		//상담에 필요한 기간 저장 배열
	public static int[] P;		//상담으로 받는 금액 저장 배열
	public static int max = Integer.MIN_VALUE;		//최대값
    public static void main(String[] args) throws IOException{
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //입력값 처리하는 BufferdReader
    	BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        //결과값 출력하는 BufferedWriter
        //-------------입력값 저장 및 배열 초기화-----------
    	int N = Integer.parseInt(br.readLine());
    	StringTokenizer st;
    	T = new int[N+1];
    	P = new int[N+1];
    	for(int i=1;i<=N;i++) {
    		st = new StringTokenizer(br.readLine()," ");
    		T[i] = Integer.parseInt(st.nextToken());
    		P[i] = Integer.parseInt(st.nextToken());
    	}
    	bestCost(N, 1, 0,0);		//함수 실행
    	bw.write(max + "\n");		//최대값 BufferedWriter 저장
    	bw.flush();			//결과 출력
    	bw.close();
    	br.close();
    }
    //--------모든 상담 경우의 수에서 받을 수 있는 금액에 최대값 구하는 함수-----
    public static void bestCost(int N, int cur, int cost, int lastCost) {
    	if(cur>N+1) {		//상담 기간이 퇴근 기간 넘어갈 경우 취소
    		max = Math.max(max, cost-lastCost);
    		return;
    	}else if(cur==N+1) {	//상담 기간이 퇴근 기간과 딱 맞을 경우
    		max = Math.max(max, cost);
    		return;
    	}
    	for(int i=cur;i<=N;i++) {		//재귀를 통한 모든 상담 경우의 수 구하기
    		bestCost(N, i+T[i], cost + P[i], P[i]);
    	}
    }
}