무서운 아르바이트(12846)

ChaeChae's Blog 2025. 2. 19. 20:29

문제설명

성화는 악독하기로 유명한 편의점 사장이다. 그의 편의점에는 특이한 임금 체계를 가지고 있다.

각 날마다 일의 차이때문에 일마다 급여가 정해져 있다.
돈은 당일에 주지 않고 퇴직을 할 때 한번에 준다.
성화는 욕심쟁이라서 해당 일을 한 동안 중 가장 일급이 작을 때를 기준으로 급여를 지급한다.
일급이 다른 것을 들키지 않기 위하여 한번이라도 퇴직한 자를 다시 취직 시키지 않는다. (만약 취직을 한다면, 일을 시작 한 날부터 끝날 때까지 하루도 빠지면 안 된다.)

준수는 n+1일 후에 001에 월세를 내야 해서 성화가 사장으로 있는 편의점에 취직하려 한다. 다행히 주변 퇴직자들의 얘기로 급여에 관련해 파악했다. 또한 퇴직자들의 급여 통계를 통해 당장 n일 후까지 일급 정보를 알아냈다. 최대로 많이 일했을 때가 최대 이익이 아닐 수 있다.

어제까지 과제를 제출하고 지금도 001에서 자고 있는 준수를 위해 코딩 잘하는 여러분이 일을 해서 벌 수 있는 최대 이익을 준수에게 알려주도록 하자.

입력

일을 할 수 있는 날의 수 (0 < n ≤ 100000) 가 주어진다.

그 다음 줄 에는 1일부터 n일 까지 일급 Ti 가 순서대로 주어진다. (0 < Ti ≤ 1,000,000)

출력

준수가 일을 해서 벌 수 있는 최대 이익을 출력한다.

문제풀이

최대 이익을 내려면, 일하는 기간 * 일하는 기간 받을 수 있는 최소 급여가 최대인 값을 구하면 된다.

분할정복 개념을 이용해 다음과 같이 해결할 수 있다.

1. 급여 배열을 최저 급여 기준으로 분할한다.

2. 급여 배열의 길이가 1이 될때까지 1번을 반복한다.

3. 분할한 최저 급여 기준으로 받을 수 있는 최대 급여를 계산한다.

const fs = require('fs');
const input = fs.readFileSync('./input.txt').toString().trim().split('\n');
const N = Number(input[0]);
const salary = input[1].split(" ").map(Number);
let answer = 0;

// 최소 급여 찾는 함수
const findMinIdx = (arr) => {
    let idx = 0;
    for (let i = 1; i < arr.length; i++) {
        if (arr[i] < arr[idx]) idx = i;
    }
    return idx;
}

const divide = (arr) => {
    let [left, right] = [null, null];
    if (arr.length <= 1) return arr; // 배열의 길이가 1이면 종료
    
    const minIdx = findMinIdx(arr);
    
    if(minIdx === 0){
        left = divide(arr.slice(0, minIdx+1))
        right = divide(arr.slice(minIdx+1))
    }else if(minIdx == arr.length -1){
        left = divide(arr.slice(0, minIdx))
        right = divide(arr.slice(minIdx))
    }else {
        left = divide(arr.slice(0, minIdx+1))
        right = divide(arr.slice(minIdx+1))
    }
    answer = Math.max(answer, arr[minIdx] * arr.length) // 해당기간에 최저 급여로 받을 수 있는 이익 중 최대값을 유지 
    return [...left, ...right]
}

if(salary.length == 1){ // 하루 일하면 당일 급여받음
    answer = salary[0];
}else {
    divide(salary);
}
console.log(answer)console.log(answer)

입력이 [10, 20, 30, 20, 10] 일 경우, 다음 표처럼 결과가 나온다.

minIdx	left	right	answer
0	[10]	[20, 30, 20, 10]	10 * 5 = 50
3	[20, 30, 20]	[10]	10 * 4 = 40
0	[20]	[30, 20]	20 * 3 = 60
1	[30]	[20]	20 * 2 = 40

answer 값을 최댓값으로 유지하고 출력해주면 정답이다.!

후기

분할정복을 할때 어떤 값을 기준으로 분할할 것인지를 찾는 과정이 어려웠다...

그리고 배열의 최솟값 인덱스가 경우에 따라 slice()를 하는 경우, 내가 생각하는 결과값이 나오질 않아서 고민하다 결국 조건문으로 해결했다.

참고로 이 문제는 분할정복으로도 풀이할 수 있지만, 모노톤 스택으로도 해결할 수 있어서 다음에는 모노톤 스택으로 풀어봐야겠다.💪