자바(백준) 14501 퇴사

오답 노트 & 새로 알게 된 점

처음에 문제 접근하여 코드를 작성했을 때, 마지막 예제를 고려하지 않았다. 그래서 해당 index에 접근하면 무조건 index의 day만큼 다음 index를 접근하게 했다. 그러나 4번 예제에서는 1번 날, 6일 날, 8일 날 접근하여 총 90이 나온다.

 

제일 이해하지 못했던 것이 과연 N+1날에는 상담을 할 수 있는 것이냐 없는 것이냐가 헷갈렸다.

예제 2번을 보면, 답이 55이다. 그렇다면 1 ~ 10을 모두 더했다는 것이다. 그러면 마지막 9번째 index는 1일이 걸리는데, 1일은 그다음 N+1번째까지 포함한다는 뜻이다. 그래서 N+1날까지 상담을 진행하는 뜻인 것 같다.

 

문제 풀이는 재귀를 사용하여 풀었다. 다른 블로그들을 보면 dp로 풀었는데 아직 dp쪽은 공부를 하지 않아,, 최대한 사용하지 않으려고 했다. 나중에 dp 공부하면 꼭 다시 풀어봐야지 했다!

 

코드

package BruteForce_Search;
 
//BOJ 14501 퇴사
 
import java.io.*;
import java.util.*;
 
public class BOJ14501 {
    static int atoi(String str){
        return Integer.parseInt(str);
    }
    static Company com[];
    static int result;
    public static void main(String args[]) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
 
        int size = atoi(st.nextToken());
        com = new Company[size];
 
        for(int i = 0; i < size; i++){
            st = new StringTokenizer(br.readLine());
            com[i] = new Company(atoi(st.nextToken()), atoi(st.nextToken()));
        }
        findMax(0,0);
        System.out.print(result);
    }
    static void findMax(int index, int money){
        if(index >= com.length){
            result = Math.max(result, money);
            return;
        }
 
        if(index + com[index].day <= com.length)
            findMax(index + com[index].day, money + com[index].money);
        else
            findMax(index + com[index].day, money);
 
        //시작점을 다음날로 하는거
        findMax(index + 1, money);
    }
}
 
class Company{
    int money, day;
 
    Company(int day, int money){
        this.day = day;
        this.money = money;
    }
}