[알고리즘 TIL] Q13458(구현), Q14501(백트래킹)

Q13458. 시험 감독

문제 

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

트러블 슈팅

 

1. int 타입 범위
int는 음의 값과 양의 값 모두를 표현할 수 있으며, 약 21억 정도의 값을 표현할 수 있다.
따라서 해당 문제의 정답으로 나올 수 있는 값은 100만 * 100만 > 21억이므로, int 타입으로 표현할 수 없다. 
변수를 모두 long으로 변환해야한다.

 

2. 나눗셈 과정에서 double 변환
int 타입의 나눗셈 과정에서 오류를 겪었다. 처음에 나눈 값에 올림하여 감독관 수를 구하기 위해 다음과 같이 구현하였다.

answer +=(int) Math.ceil(class[i]/C);

위와 같이 구현하면, class[i] / C 가 int 타입 / int 타입이라, int 타입으로 결과가 나온다. 즉, 0.15가 아닌, 0이 나오고, 올림을 하여도 원하는 1이 아닌 0이 나오게 되었다.

 

따라서 다음과 같이 수정하였다.

double doubleNum = (double) classes[i]/C;
answer +=(int) Math.ceil(doubleNum);

classes[i]나 C 중 하나를 double 타입으로 수정하면, 값도 double로 나온다.

(classes[i]/C를 묶으면 또 int 타입으로 먼저 결과가 나오므로 안된다.)

 

구현

import java.io.*;

public class Q13458 {

    static long N, B, C;
    static long answer;
    //answer가 백만*백만(총 수강생 수) 일 있으므로 int 타입으로 불가!
    //숫자가 좀 크면 long 고려햐기
    static long[] classes;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        N = Integer.parseInt(br.readLine());
        classes = new long[(int)N];

        String[] inputStrArr = br.readLine().split(" ");
        for (int i = 0; i < N; i++) {
            classes[i] = Integer.parseInt(inputStrArr[i]);
        }

        inputStrArr = br.readLine().split(" ");
        B = Integer.parseInt(inputStrArr[0]);
        C = Integer.parseInt(inputStrArr[1]);

        answer = 0;

        for (int i = 0; i < N; i++) {
            classes[i] -= B;
        }
        answer += N;

        for (int i = 0; i < N; i++) {
            if (classes[i] > 0) {
                double doubleNum = (double) classes[i]/C; //묶으면 안되는게 묶으면 int로 내림됨 -> double 해봣자 0나옴 하나만 double로 바꿔야 제대로 계산됨
                 answer +=(int) Math.ceil(doubleNum); //Math의 함수는 인자로 소수가 들어와야 제대로 작동하므로, 꼭 double로 따로 계산해서 넣어보자
                //반올림: round(), 올림: ceil(), 내림: floor()
            }
        }
        bw.write(answer + "");

        bw.flush();
        bw.close();
        br.close();
    }
}

Q14501. 퇴사

문제

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

트러블 슈팅

 

1. 백트래킹 알고리즘 구현

일하는 날과 임금까지 고려하여 최적의 방법을 찾기 위해 그리디 알고리즘은 사용할 수 없다고 판단하긴 했는데, 백트래킹까지 떠올리지는 못했다. 또한, 재귀함수의 구조 또한 구현하지 못했다.

 

백트래킹은 재귀함수를 사용하여, 필요 없는 경우를 가지치기(pruning)함으로써 시간복잡도를 줄이는 방법이다.

void backtrack(현재 상태) {
    if (종료 조건 만족) {
        정답 갱신;
        return;
    }

    for (가능한 선택들) {
        상태 변화;
        backtrack(다음 상태);
        상태 복원; // (있다면)
    }
}

 

퇴사 문제와 백트래킹 전형적인 구조 비교는 다음과 같다.

구성 요소	퇴사 문제	백트래킹에서의 구현 충족 여부
종료 조건	if (day >= N) → 퇴사일을 넘어가면 종료	✅
정답 갱신	result = Math.max(...)	✅
가능한 선택 반복	고정된 2가지 선택: "상담함", "안 함"	✅
상태 변화	day + t, profit + p	✅
상태 복원	❌ 별도 복원 없음 (→ 불필요하므로 생략 가능)	✅

 

2. 누적 임금을 넘기는 타이밍

처음에는, 다음과 같이 구현하였다.

private static void backtracking(int day, int prevDay, int gatheringMoney) {
        //종료 조건(이미 일할 수 있는 남은 날을 지났을 때)
        if (day >= totalWorkingDay) {
            // 일 못하면 돈 제외
            gatheringMoney -= workAndPayData[prevDay][1];
            // 모은 돈이 이전 먼저 종료된 백트래킹에서 모은 돈보다 큰 지 확인
            result = Math.max(result, gatheringMoney);
            return;
        }

        int workPeriod = workAndPayData[day][0];
        int pay = workAndPayData[day][1];

        //day에 일하는 재귀
        backtracking(day + workAndPayData[day][0], day ,gatheringMoney + workAndPayData[day][1]);

        //day에 일안하는 재귀
        backtracking(day + 1, day, gatheringMoney);
    }

 

하지만, 퇴사일을 넘었는지 확인은 “일 시작할 때” 해야지 “끝날 때 돈 빼는 방식”은 논리 오류이다. 끝날 때 돈 빼면 마지막 날에 일 안하는 걸 택했는데 이전에 정당하게 번 돈까지 빼버리기 때문이다.

 

따라서, 일하는 재귀는 무조건 행하지 않고, 가능한 경우만 실행하도록 한다.

private static void backtracking(int day, int gatheringMoney) {
        //종료 조건(이미 일할 수 있는 남은 날을 지났을 때)
        if (day >= totalWorkingDay) {
            // 모은 돈이 이전 먼저 종료된 백트래킹에서 모은 돈보다 큰 지 확인
            result = Math.max(result, gatheringMoney);
            return;
        }

        int workPeriod = workAndPayData[day][0];
        int pay = workAndPayData[day][1];

        // 현재 일정을 선택할 수 있는 경우
        if (day + workPeriod <= totalWorkingDay) {
            backtracking(day + workPeriod, gatheringMoney + pay);
        }

        // 현재 일정을 선택안하는 겨우
        backtracking(day + 1, gatheringMoney);
    }

구현

import java.io.*;

public class Q14501 {

    static int[][] workAndPayData;
    static int result = 0;
    static int totalWorkingDay;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        totalWorkingDay = Integer.parseInt(br.readLine());
        workAndPayData = new int[totalWorkingDay][2];

        for (int i = 0; i < totalWorkingDay; i++) {
            String[] inputStrArr = br.readLine().split(" ");
            workAndPayData[i][0] = Integer.parseInt(inputStrArr[0]);
            workAndPayData[i][1] = Integer.parseInt(inputStrArr[1]);
        }

        backtracking(0,0);
        bw.write(result + "");

        bw.flush();
        bw.close();
        bw.close();
    }

    private static void backtracking(int day, int gatheringMoney) {
        //종료 조건(이미 일할 수 있는 남은 날을 지났을 때)
        if (day >= totalWorkingDay) {
            // 모은 돈이 이전 먼저 종료된 백트래킹에서 모은 돈보다 큰 지 확인
            result = Math.max(result, gatheringMoney);
            return;
        }

        int workPeriod = workAndPayData[day][0];
        int pay = workAndPayData[day][1];

        // 현재 일정을 선택할 수 있는 경우
        if (day + workPeriod <= totalWorkingDay) {
            backtracking(day + workPeriod, gatheringMoney + pay);
        }

        // 현재 일정을 선택안하는 겨우
        backtracking(day + 1, gatheringMoney);
    }
}