[백준, 21847] 꿀 아르바이트(java)

문제 설명

준수는 윤호의 편의점에서 일을 하려고 한다. 윤호의 편의점은 각 날마다 급여가 다르고 일급을 따박따박 당일마다 준다. 또한 정해진 일 수 만큼만 일을 시키고 한 번 취직을 하면 끝날 때까지 하루라도 빠질 수 없다.

 

준수는 윤호의 편의점의 n일 후까지 일급 정보를 알아냈다. 다만, 준수는 m일 밖에 일할 수 없다. 그렇기에 준수가 윤호네 편의점에서 m일을 일하고 얻을 수 있는 최대 이익을 알려주자.

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

12847번: 꿀 아르바이트

기본적인 슬라이딩 윈도우 알고리즘이다.

다만, 나는 여기서 예상보다 시간을 많이 썼는데 그 이유는 입력의 조건을 제대로 읽지 않았기 때문이다. 

윤호네 편의점에서 주는 급여는 0부터 1,000,000까지이다. 준수는 최대 100,000일을 일할 수 있으므로 준수가 받을 수 있는 최대 이익은 100,000,000,000이다. 그러므로 여기서는 long 형을 사용해야 한다.

 

나는 윤호네 편의점의 일급이 이렇게 좋다는 것을 모르고(?!) int로 해버려서 혼란스러운 시간을 겪었다.

문제 풀이

슬라이딩 윈도우로 풀어주면 된다.

슬라이딩 윈도우란 정해진 범위를 계속 앞으로 밀어주면서 해당 범위에 있는 연산을 진행하는 알고리즘이다.

 

슬라이딩 윈도우를 사용하지 않고 해당 문제를 풀면 2차 반복문을 사용해야 해서 시간 복잡도가 O(n^2)이 나온다. 문제에서 n의 최대 값은 1,000,000이니까 2차 반복문을 쓰면 1,000,000,000,000이 걸리니까. 음... 1억에 1초 정도라고 생각하면 좀 곤란할지도?

 

아무튼! 슬라이딩 윈도우는 범위를 정해놓고 앞으로 밀며 새 값을 더하고 뒤에 있는 값을 빼주는 방식으로 움직인다. 그러므로 O(n)이 걸려서 안전하게 조건을 맞출 수 있다.

 

슬라이딩 윈도우를 푸는 방법은 여러 가지가 있는데, 나는 start와 end 인덱스를 잡고 while문을 돌리면서 풀었다. while문의 조건이 end가 n-1보다 작을 때인 이유는 조건 문 안에서 end를 1개 씩 더해주기 때문이다. 만일 end를 n보다 작을 때라고 잡으면 end++를 했을 때 IndexOutOfBound가 날 것이므로 조건을 n-1보다 작을 때로 했다.

코드

java1

import java.util.*;
import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
        st = new StringTokenizer(br.readLine());
        List<Long> wage = new ArrayList<>();
        while(st.hasMoreTokens()) {
            wage.add(Long.parseLong(st.nextToken()));
        }

        long sum = 0;
        for (int i=0; i<m; i++) {
            sum += wage.get(i);
        }

        int start = 0;
        int end = m-1;
        long answer = sum;
        while(end < n-1) {
            sum -= wage.get(start);
            start++;
            end++;
            sum += wage.get(end);
            answer = Math.max(answer, sum);
        }

        System.out.println(answer);
    }

}

java2

import java.util.*;
import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
        st = new StringTokenizer(br.readLine());
        List<Long> wage = new ArrayList<>();
        while(st.hasMoreTokens()) {
            wage.add(Long.parseLong(st.nextToken()));
        }

        long sum = 0;
        for (int i=0; i<m; i++) {
            sum += wage.get(i);
        }

        long answer = sum;
        for (int i=0; i<n-m; i++) {
            sum -= wage.get(i);
            sum += wage.get(i+m);
            answer = Math.max(sum, answer);
        }

        System.out.println(answer);
    }

}