[백준 BOJ] 2828번 사과 담기 게임 (C++/cpp)

문제 설명

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

2828번: 사과 담기 게임

 

접근 방법 - 사칙연산을 이용한 그리디 알고리즘 문제

백준의 2828번 문제는 사칙연산을 이용하여 해결할 수 있는 그리디 알고리즘 문제이다.

해당 문제는, 주어진 크기의 스크린과 바구니를 이용한 게임에서 모든 사과를 담기 위한 최소 이동 횟수를 구하여 출력해야 하는 문제이다.

이때 "최소" 이동 횟수이기 때문에, 바구니 범위에 있지 않는 사과는 바구니의 끄트머리에서 받게끔 이동해야 할 것이다.

따라서 필자는, 바구니의 시작점과 끝점에 의의를 두면 문제 해결을 시도해 보았다.

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

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

 

코드의 실행 순서

1) 스크린의 크기(n), 바구니의 크기(m), 떨어지는 사과의 개수(j)를 순차적으로 입력받는다.

 

2) 문제를 참고하였을 때, 처음 바구니는 스크린의 가장 왼쪽에 자리하고 있다고 명시되어 있다.

따라서, 바구니의 시작을 가리키는 변수 basket을 선언함과 동시에 1로 초기화하도록 한다.

잇따라, 정답인 최소 이동 횟수를 저장할 변수 result는 0으로 초기화하면서 선언한다.

 

3) j의 크기만큼, 반복문을 수행하여 아래의 연산을 취한다.

- 스크린 상 사과가 떨어지는 지점(num)을 순차적으로 입력받는다.

- 만일 num이 basket보다 작은 값을 갖고 있다면, 바구니가 닿지 않는 왼쪽 지점에서 사과가 떨어지고 있음을 의미한다.

따라서 이 경우에는, 바구니의 시작점이 num에 닿을 때까지 basket의 값을 1씩 빼면서 바구니를 왼쪽으로 이동한다. 그와 동시에, 이동 횟수인 result에 1씩 더하도록 한다.

- 다만 num이 (basket+m-1) 값보다 큰 값을 갖고 있다면, 바구니가 닿지 않는 오른쪽 지점에서 사과가 떨어지고 있음을 의미한다.

따라서 이 경우에는, 바구니의 끝점이 num에 닿을 때까지 basket의 값을 1씩 더하면서 바구니를 오른쪽으로 이동한다. 그와 동시에, result에 1씩 더하도록 한다.

(위 2가지를 제외한 상황에서는 바구니를 이동하지 않아도 사과를 담을 수 있기 때문에, 특별히 수행할 연산은 없다.)

 

4) 3)의 연산이 모두 완료되었다면, 최종적으로 저장된 result의 값을 출력하면서 실행 종료한다.

반응형

 

성공한 코드

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

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

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

	int basket = 1;
	int result = 0;
	for (int i = 0; i < j; i++) {
		int num;
		cin >> num;

		if (basket > num) {
			while (basket != num) {
				basket--;	result++;
			}
		}
		else if (basket + m - 1 < num) {
			while (basket + m - 1 != num) {
				basket++;	result++;
			}
		}
	}

	cout << result << endl;
}

 

제출 결과

(2023.08.06 백준 2828번 문제 제출 결과)