백준 17420번 깊콘이 넘쳐흘러

- 문제 설명

 

기프티콘 N개 선물 받은 정우는 기한 연장을 최소 횟수로 연장을 하면서 기프티콘을 다 쓸 수 있도록 하고 싶다.

 

- 조건

1) 한 기프티콘을 한 번 연장할 때마다 기한이 30일씩 늘어난다.

2) 남은 기프티콘 중 기한이 가장 적게 남은 기프티콘만 사용할 수 있다.

3) 하루에 여러 기프티콘을 사용하거나 연장하는 것 모두 가능하다.

 

 

- 입력

 

첫 째 줄에 기프티콘의 수 N 이 주어진다. (1 <= N <= 100,000)

둘 째 줄에 A₁ ... A_N 가 주어진다. 이는 i번째 기프티콘의 남은 기한이 A_i일이라는 뜻이다.

셋 째 줄에 B₁ ... B_N 가 주어진다. 이는 i번째 기프티콘을 B_i일 뒤에 사용할 계획이라는 뜻이다.

 

 

- 출력

 

첫 째 줄에 정우가 기한 연장을 해야 하는 최소 횟수를 출력한다.

 

정답이 32비트 정수를 넘을 수 있으므로 유의하라.

 

 

* 문제 풀이의 핵심

 

1. 남은 기프티콘 중 기한이 가장 적게 남은 기프티콘만 사용할 수 있다.

 

- 이전 구간의 최댓값 보다 크고, 현재 구간의 B_i 값보다 큰 수 이상으로 기프티콘 일 수를 연장해야 한다.

 

 

기프티콘 연장 횟수 정하는 방법

 

 

2. 로직

 

1) 우선 B_i 순 오름차순 정렬, 값이 같다면 A_i 순 오름차순 정렬

 

2) for 문으로 array를 순회한다.

 

 

2-1) 이전 구간의 최댓값이 A_i 보다 클 경우

 

2-1-1) 이전 구간의 최댓값 보다 기프티콘 사용 예정일이 더 크다면 갱신

 

2-1-2) 3.2) 를 기준으로 연장 횟수 계산

 

2-1-3) answer 값을 횟수 만큼 증가

 

 

2-2) 그렇지 않은 경우

 

2-2-1) 같은 구간의 최댓값을 찾기 위해 갱신된 A_i 값의 최댓값 찾기

 

 

2-3) 구간 변경 시 같은 현재 구간 값 중 최댓값을 이전 구간의 최댓값으로 갱신

 

 

3. 기타

 

1) 정답이 32비트 정수를 넘을 수 있으므로 유의하라.

- 정수형 범위를 벗어나는 출력 값이 존재하므로 long long 자료형으로 최소 횟수를 카운팅 한다.

 

2) 나머지 계산

- 연장 횟수 : (30일의 몫 + (30일의 나머지가 있을 경우 횟수 1 추가)) 

- 30일의 나머지를 if 문으로 계산하지 않고 29를 더하면 몫을 바로 계산 할 수 있다.

 

 

- 소스코드

 

#include<iostream>
#include<algorithm>
#include<vector>

using namespace std;

int A[100001];
int B[100001];

typedef struct TASK {
	int A;
	int B;
} TASK;

vector<TASK> arr;

bool cmp(TASK a, TASK b) {
	if (a.B == b.B) {
		return a.A < b.A;
	}
	else {
		return a.B < b.B;
	}
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int N;
	cin >> N;

	int i;
	for (i = 0; i < N; i++) {
		cin >> A[i];
	}

	for (i = 0; i < N; i++) {
		cin >> B[i];
	}

	for (i = 0; i < N; i++) {
		arr.push_back({ A[i], B[i] });
	}

	// 32 비트 정수 초과 경우 고려
	long long answer = 0;

	sort(arr.begin(), arr.end(), cmp);

	int prev_max = arr[0].B;
	int cur_max = -1;

	for (i = 0; i < N; i++) {
		if (prev_max > arr[i].A) {
			// 이전 구간의 최댓값 보다 기프티콘 사용날짜가 더 크다면 갱신
			if (prev_max < arr[i].B) prev_max = arr[i].B;

			// 29를 더해주면 나머지가 1이상일 때 몫을 1추가한 것과 같다.
			int cnt = ((prev_max - arr[i].A) + 29) / 30;
			arr[i].A += (cnt * 30);

			answer += cnt;
		}

		// 같은 구간의 최댓값 찾기
		cur_max = max(cur_max, arr[i].A);

		// 구간 변경시 같은 구간 값중 최댓값을 이전값으로 갱신
		if ((i + 1) < N && arr[i].B != arr[i + 1].B) {		
			prev_max = cur_max;
		}
	}

	cout << answer << "\n";
}

/* 반례
5
24 2 3 29 2
25 30 30 30 35

*/

 

 

- 문제링크 : www.acmicpc.net/problem/17420

17420번: 깊콘이 넘쳐흘러

 

 

- 제출한 코드

 

 

>  백준 아이디 : canoe726

>  사용언어 : C++

>  에디터 : Visual Studio 2017

>  궁금한점은 댓글로 남겨주세요

 

 

- 출처

1) 티스토리 블로그 : aruz.tistory.com/entry/17420