백준 - 12847 (Java)
문제
윤호는 퍼주기로 유명한 편의점 사장이다. 그의 편의점에는 특이한 임금 체계를 가지고 있다.
- 각 날마다 일의 차이때문에 일마다 급여가 정해져 있다.
- 윤호는 오차 없이 일급을 따박 따박 당일에 준다.
- 정해진 일 수 만큼만 일을 시킨다.
- 한번이라도 퇴직한 자를 다시 취직 시키지 않는다. (만약 취직을 한다면, 일을 시작 한 날부터 끝날 때까지 하루도 빠지면 안 된다.)
무서운 아르바이트를 짤린 준수는 n+1일 후에 001에 월세를 내야 해서 윤호가 사장으로 있는 편의점에 취직하려 한다. 다행히 주변 퇴직자들의 얘기로 급여에 관련해 파악했다. 또한 퇴직자들의 급여 통계를 통해 당장 n일 후까지 일급 정보를 알아냈다. 하지만 준수는 시험을 준비해야 하기에 최대 m일 밖에 일을 할 수 없다.
어제까지 과제를 제출하고 지금도 001에서 자고 있는 준수를 위해 코딩 잘하는 여러분이 일을 해서 벌 수 있는 최대 이익을 준수에게 또 알려주도록 하자.
입력
월세를 내기 바로 전 날 까지 인 n (1 ≤ n ≤ 100,000) 일과 일을 할 수 있는 날 m (0 ≤ m ≤ n) 일이 주어진다.
그 다음 줄 에는 1일부터 n일 까지 일급 Ti가 순서대로 주어진다. (0 < Ti ≤ 1,000,000)
출력
준수가 일을 해서 벌 수 있는 최대 이익을 출력한다.
예제 입력 1
5 3
10 20 30 20 10
예제 출력 1
70문제접근
제일 간단한 문제로는 loop를 돌며 일마다 일할 수 있는 연속 기간동안 추가 loop를 통해 합을 구해 비교하면 간단하게 구현 할 수있지만 O(n^2)의 시간 복잡도를 가지게 된다.
이를 해결하기 위해 제일 첫번째 날만 연속기간 일당을 구한 뒤 다음날 일자를 구할때는 해당 합에서 전날의 일당을 빼고 추가된 일당을 더해서 최대 이익을 구하는 방법으로 구현하였다.
- 0일 부터 N - M 일까지 loop를 돈다.
- 0일의 경우 0일 ~ M일 까지의 누적 합을 구한다.
- 0일이 아닌 경우 전날짜의 임금을 빼고 다음날짜를 합한다.
- 누적합이 이전 누적합의 최댓값보다 크면 최신화 한다.
++ 합계를 구하는 변수가 int로 선언 된 경우 범위를 초과하여 오답처리 되었다. 해당 변수를 long 으로 변경한 이후 정상적으로 정답 처리 될 수 있었다.
문제풀이
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringTokenizer st;
st = new StringTokenizer(br.readLine());
int N = Integer.parseInt(st.nextToken());
int day = Integer.parseInt(st.nextToken());
int[] arr = new int[N];
st = new StringTokenizer(br.readLine());
for(int i = 0; i < N; i++)
arr[i] = Integer.parseInt(st.nextToken());
long maxProfit = 0;
long tempSum = 0;
for(int i = 0; i < N - day + 1; i++) { // #1
if(i == 0) { // #2
for(int j = 0; j < day; j++)
tempSum += arr[j];
}else { // #3
tempSum -= arr[i-1];
tempSum += arr[i + day-1];
}
//System.out.println(i + " " + (i+day) + " " + arr[i+day-1] + " " + tempSum);
if(tempSum > maxProfit) // #4
maxProfit = tempSum;
}
bw.write(maxProfit + "");
bw.flush();
br.close();
bw.close();
}
}