[백준 BOJ] 12847번 꿀 아르바이트 (C++/cpp)

문제 설명

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

 

 

접근 방법 - 슬라이딩 윈도우를 활용한 투 포인터 응용문제

백준의 12847번 문제는 슬라이딩 윈도우 기법을 활용하여 쉽게 해결할 수 있는 투 포인터 문제이다.

해당 문제는, 주어진 각 날짜의 급여에 대해서 정해진 일수만큼 연속으로 일할 수 있을 때 최대로 벌어들일 수 있는 급여를 구하여 출력해야 하는 문제이다.

슬라이딩 윈도우를 그대로 문제에 적용하여, 시작 및 끝 포인터로 활용할 변수를 한 칸씩 이동하면서 최댓값을 찾아내기만 하면 되기 때문에, 이 기법만 잘 알고 있다면 어렵지 않게 해결할 수 있을 것이다.

이때, 주어진 일급 중에서 연속으로 받을 수 있는 이익 중 최대를 구해야 하기 때문에, 슬라이딩 윈도우 기법을 사용할 때 총액 값에도 변동을 주면서 연산을 진행해야 할 것이다. (누적합을 활용해야 한다는 뜻이다.)

자세한 설명은 아래에서 진행하니, 혹여나 해당 문제를 해결하는 데에 어려움을 겪고 있다면 아래의 설명 및 코드를 참고해 보길 바란다.

필자는 아래의 순서대로 코드를 작성하여 문제를 해결하였다.

 

코드의 실행 순서

1) 일급의 개수(n)와 일을 연속으로 할 수 있는 일수(m)를 입력받는다.

 

2) n개의 일급을 입력받을 벡터 money를 미리 선언해 둔다. 

그리고 슬라이딩 윈도우 기법을 활용하여, m일간의 총 일급들을 연산할 변수 sum을 0으로 초기화하여 선언해 둔다.

필자는 테스트 케이스의 입력값들 범위를 확인하면서, sum을 미리 long long int형으로 선언해 두었다.

 

3) n개의 일급을 입력받고, 이들을 money에 순차적으로 삽입한다.

그와 동시에, 0 ~ m-1(총 m일) 구간의 입력값들을 sum에 추가한다.

(필자는 여기에서의 sum값을 시작으로 하여, 이에 변동을 주면서 최대 이익을 탐색할 예정이다.)

 

4) 3)에서 연산한 sum값은 0 ~ m-1 일급의 총액이기 때문에, 이에 맞추어 시작 및 끝 포인터 변수를 초기화한다.

시작 포인터인 start 변수는 0으로, 끝 포인터인 end 변수는 m-1로 초기화한다.

그리고 정답인 최대 이익을 저장할 변수 max를 선언하고, 이 변수의 초기값은 3)의 sum 값으로 우선 설정해 둔다.

 

5) 무한 반복문으로 설정해 두고, 아래의 연산을 반복으로 수행하도록 한다.

(여기서는, 구간의 크기는 m으로 유지하면서 구간의 위치를 옆으로 점차 이동하려 한다. 이것이 슬라이딩 윈도우 기법이다.)

- 구간의 시작인 start를 옆으로 한 칸 이동시킨다.

이때 다음 구간에서는 해당 일급을 빼야 하기 때문에, start 위치의 일급을 sum에서 뺀 다음에 start++를 진행하도록 한다.

- 구간의 끝인 end를 옆으로 한 칸 이동시킨다. 

이때 다음 구간에서는 다음 날의 일급을 추가로 더해야 하기 때문에, end++를 수행한 뒤에 end 위치의 일급을 sum에 더하도록 한다.

(필자는 반복문의 중단점을 end 변수를 연산하는 부분에 걸어두었다. end++의 결과로 end가 n과 같아졌다면, 이는 더 이상 탐색할 구간이 없음을 의미하기 때문에 break를 수행하여 해당 반복문을 빠져나오게끔 하였다.)

- 반복문이 끝나지 않았다면, max와 현재 sum값을 비교한다.

만약 현재 max보다 더 큰 sum값이 나타났다면, 해당 sum값으로 max를 갱신한다.

 

6) 위 연산이 모두 수행되었다면, 최종적으로 저장된 max를 출력한 뒤 실행 종료한다.

반응형

 

성공한 코드

#define _CRT_SECURE_NO_WARNINGS
#pragma warning(disable: 4996)
#include <iostream>
#include <vector>
#define endl '\n'
using namespace std;

//백준 12847번 코드
int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);	cout.tie(NULL);

	int n, m;
	cin >> n >> m;

	vector<int> money;
	long long int sum = 0;
	for (int i = 0; i < n; i++) {
		int num;
		cin >> num;

		money.push_back(num);
		if (i < m) { sum += num; }
	}

	int start = 0;
	int end = m - 1;
	long long int max = sum;
	while (true) {
		sum -= money[start];
		start++;
		end++;
		if (end >= n) { break; }
		else {
			sum += money[end];
		}

		if (max < sum) { max = sum; }
	}
	cout << max << endl;
}

 

제출 결과

(2023.12.15 백준 12847번 문제 제출 결과)