백준 - 지금 자면 꿈을 꾸지만(32029)

⭐문제링크

문제 요약

실버는 N개의 과제가 있으며, 각 과제는 특정 기한(Ti)을 가지고 있습니다. 실버는 다음과 같은 방식으로 과제를 진행할 수 있습니다:

과제 완료 시간 : A 시간.

but??? 잠을 자게 된다면

자는 시간 : BX 시간
과제 완료 시간 : (A − X) 시간

여기서 X는 0 이상 (A − 1) 이하의 정수입니다.

실버는 잠을 최대 한 번 잘 수 있으며, 과제를 진행하는 도중에는 잠을 잘 수 없습니다

실버의 목표는 기한 내에 최대한 많은 과제를 완료하는 것입니다. 과제를 기한 내에 완료한다는 것은 과제를 기한 Ti 이전 또는 정확히 Ti에 완료하는 것을 의미 합니다.

풀이

해당 문제는 그냥 브루트포스로 돌려야 합니다.

즉 I의 범위 ( 1에서 N ) 에서 I-1 번째에는 잠을 자고 과제를 하는 경우, 모든 X의 범위 ( 0에서 A-1 ) 에서 과제를 하는 경우를 다 계산해야 합니다.

코드

public class Main {
    static int N;
    static int A;
    static int B;
    static int [] tasks;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken());
        A = Integer.parseInt(st.nextToken());
        B = Integer.parseInt(st.nextToken());

        tasks = new int[N+1];

        st = new StringTokenizer(br.readLine());

        for(int i=1; i<=N; i++) {
            tasks[i] = Integer.parseInt(st.nextToken());
        }

        Arrays.sort(tasks);

        int answer = 0;
        for(int X = 0; X<A; X++) {
            for(int i=1; i<=N; i++) { //i-1 번째에 잠을 자고 과제를 하는 경우의 수 계산
                answer = Math.max(answer, findTasks(X, i, B*X));
            }
        }

        System.out.println(answer);
    }

    static int findTasks(int X, int start, int sleep) {
        int count = 0;
        int time=0;

        //안자고 한 과제 시간 더하기
        for(int i=1; i<start; i++) {
            time+=A;
            if( time > tasks[i] ) continue;
            count++;
        }

        //잔 시간 더하기
        time+=sleep;

        //잔 후에 과제 시간 더하기
        for(int i = start; i<=N; i++) {
            time+=(A-X)
            if(time > tasks[i]) continue;
            count++;
        }

       return count;
    }

}

해당 코드는 실패 코드입니다.

왜냐면 한 가지 반례 때문입니다.

현재 제 코드 내 과제 수행 과정은 다음과 같습니다.

[실패 코드 전략]

1. 일단 과제 수행시간 만큼 과제를 함
2. 1번에서 진행한 과제(T)가 마감기한을 넘겼는지 확인(Ti)
   2-1. 마감기한 넘겼다면 -> 과제 못냄
   2-2. 마감기한 안넘겼다면 -> 과제 냄

그러나 위와 같은 과정은 과제를 낼 수 없어도 무조건 시간을 써버리기에,
너무 짧은 마감기한을 가진 과제에는 시간을 쏟지 말고 넘어가야 하는데 해당 경우를 거르지 못합니다.

즉 반례는 아래와 같습니다.

반례)
2 10 20
11 12

그렇기 때문에 로직을 변경하였습니다.

[정답 코드 전략]

1. 현재 i번째 과제인 T를 Ti안에 해낼 수 있는지 확인
   1-1. 할 수 있다면 -> 과제 진행
   1-2. 할 수 없다면 -> 과제 패스

정답코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
    static int N;
    static int A;
    static int B;
    static int [] tasks;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken());
        A = Integer.parseInt(st.nextToken());
        B = Integer.parseInt(st.nextToken());

        tasks = new int[N+1];

        st = new StringTokenizer(br.readLine());

        for(int i=1; i<=N; i++) {
            tasks[i] = Integer.parseInt(st.nextToken());
        }

        Arrays.sort(tasks);

        int answer = 0;
        for(int X = 0; X<A; X++) {
            for(int i=1; i<=N; i++) { //i-1 번째에 잠을 자고 과제를 하는 경우의 수 계산
                answer = Math.max(answer, findTasks(X, i, B*X));
            }
        }

        System.out.println(answer);
    }

    static int findTasks(int X, int start, int sleep) {
        int count = 0;
        int time=0;

        //안자고 한 과제 시간 더하기
        for(int i=1; i<start; i++) {
            if( time+A <= tasks[i] ) {
                time+=A;
                count++;
            }
        }

        //잔 시간 더하기
        time+=sleep;

        //잔 후에 과제 시간 더하기
        for(int i = start; i<=N; i++) {
            if(time+(A-X) <= tasks[i]) {
                time+=(A-X);
                count++;
            }
        }

       return count;
    }

}