[BOJ 23322 // C++] 초콜릿 뺏어 먹기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

 

이번에 볼 문제는 백준 23322번 문제인 초콜릿 뺏어 먹기이다.
문제는 아래 링크를 확인하자.

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

23322번: 초콜릿 뺏어 먹기

다음과 같은 전략으로 초콜릿을 먹는다면 항상 가장 많은 초콜릿을 최소 횟수로 먹을 수 있다.

 

1) K+1, K+2, ..., K+i, ..., N번째 통의 초콜릿을 (먹을 게 있다면) 차례대로 먹는다. 이 과정에서 i번째로 먹은 초콜릿통에 남은 초콜릿의 개수는 첫번째 통의 초콜릿의 개수와 같아진다. 또한 위 과정을 마치면 뒤의 K개의 통을 제외한 앞의 모든 통은 첫번째 통의 초콜릿과 같은 개수의 초콜릿이 남아있다는 것을 알 수 있다.

2) 이제 마지막 초콜릿통에 담겨있는 초콜릿의 개수가 첫번재 통에 남아있는 초콜릿 개수와 같아질 때까지 반복해서 먹는다.

 

이것이 최적이라는 것을 증명하는 것은 어렵지 않으므로 읽는이에게 남겨둔다.

 

아래는 제출한 소스코드이다.

#include <iostream>
using namespace std;

int N, K;

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> N >> K;
	int days = 0, cnt = 0;
	int mn; cin >> mn;
	for (int i = 1; i < N; i++) {
		int x; cin >> x;
		if (x > mn) days++, cnt += x - mn;
	}

	cout << cnt << ' ' << days;
}