[백준 BOJ/Silver III] 14501번 : 퇴사

 

https://www.acmicpc.net/problem/14501

14501번: 퇴사

 

import java.util.Scanner;

public class Main {

    static int N;
    static int[][] table;
    static int result = 0;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        table = new int[N+1][2];

        for(int i = 1; i < N+1; i++) {
            table[i][0] = sc.nextInt();
            table[i][1] = sc.nextInt();
        }

        for(int i = 1; i < N+1; i++) {
            if(i + table[i][0] - 1 <= N) {
                consult(i, table[i][1]);
            }
        }

        System.out.println(result);
    }

    static void consult(int x, int money) {
        int nx = x + table[x][0];
        if(nx > N || nx + table[nx][0] > N) {
            result = Math.max(result, money);
        }
        for(int i = nx; i < N+1; i++) {
            if(i + table[i][0] - 1 <= N) {
                consult(i, money + table[i][1]);
            }
        }
    }
}

 

- "시작하는날+걸리는기간" 이 N을 넘지 않을때 상담 가능 

-  상담 가능한 날에는 버는 돈을 계속 더해주다가 더이상 상담을 할 수 없다면 Math.max를 이용하여 이전 money들과의 비교를 통해 최대 이익으로 result값을 갱신해준다

 

 

정답을 내기 전에 실수한 부분이 있었는데

 static void consult(int x, int money) {
        int nx = x + table[x][0];
        if(nx > N || nx + table[nx][0] > N) {
            result = Math.max(result, money);
        }

        if (nx < N + 1 && nx + table[nx][0] - 1 <= N) {
            consult(nx, money + table[nx][1]);
        }
    }
}

 

이 코드였다 나머지 예제는 답이 맞고 예제 4만 틀렸는데 왜 그럴까 생각해보면서 고칠 수 있었다 이걸로 하면 최대 이익을 낼 수 있는 경우를 놓치게 되는데  

1 - 5 50
2 - 4 40
3 - 3 30
4 - 2 20
5 - 1 10
6 - 1 10
7 - 2 20
8 - 3 30
9 - 4 40
10 - 5 50

 

1일에서 시작했을때 두번째로 상담이 가능한 날은 6일이고 이때는 하루만에 완료가 되니 그 다음날을 선택해서 조건에 만족하는지 확인하고 진행한다

여기서 실수가 생기는거다!
6일 상담이 끝나고 7일을 선택할 수도 있지만 건너뛰고 8일에 해도 기간 안에 끝나기 때문에 선택이 가능하며 심지어 이게 더 최대 이익을 낸다

이걸 깨닫고 다른 경우도 생각해볼수있게 

for(int i = nx; i < N+1; i++) {

 

이거를 넣어주었다 이러면 N을 벗어나지 않는 7일에 하는경우, 8일에 하는경우 둘 다 확인해볼 수 있게 된다

 

---

 

 

⭐⭐이 문제는 dp로 푸는게 더 효율적이라고 한다 확실히 공부하고나서 dp로 다시 풀어볼 예정!!