알고리즘 :: 백준 :: 2828 - 사과 담기 게임

 

 

 

❔문제

🔗문제링크

🔄 문제 및 입출력 조건 파악

입력

• 칸 수 N, 바구니의 크기 M, (1 ≤ M < N ≤ 10)
• 사과의 개수 J (1 ≤ J ≤ 20)

출력: 바구니 이동거리 최솟값

✏️ 문제풀이

최소로 이동하기 위해서는 최대한 바구니 양끝에서 사과를 받는게 이득이라는 건 쉽게 떠올릴 수 있습니다.

• 만일 반대쪽에서 사과가 떨어진다면, 조금 덜 이동할 수 있을거고,
• 사과가 바구니 안쪽으로 떨어질 가능성도 높아질 테니까요.

 

로직 자체는 상당히 간단합니다.

1. 사과가 떨어지는 위치가 왼쪽 끝에서 가까운지 아니면 오른쪽 끝에서 가까운지 판단합니다.
2. 더 가까운 방향으로 이동합니다. 단, 딱 사과가 위치한 지점까지만 움직이면 되겠습니다.

 

그렇다면, 왼쪽을 `l`이라 하면 오른쪽 끝 `r`을 어떻게 표현할 수 있을까요?

바구니 크기 `M == 1`이라면 `r == 1`일것입니다. `M == 3`이라면, `r == l + 2`겠지요.

즉, `r = l + M - 1`로 나타낼 수 있습니다.
( 저는 그냥 매 루프마다 `r` 계산 안 하고 그냥 `l`과 `r`을 함께 끌고 갔습니다. )

📝 코드

#include <bits/stdc++.h>
using namespace std;

int N, M, J;
vector<int> apples;

int main() {
	ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
	cin >> N >> M >> J;
	while (J--) {
		int temp;
		cin >> temp;
		apples.push_back(temp);
	}
	int l = 1, r = M, result = 0, diff = 0;
	for (int pos : apples) {
        if (l <= pos && pos <= r) continue;
        if (pos < l) {	// 사과가 왼쪽
            diff = l - pos;
            l -= diff;
            r -= diff;
        } else {	// 사과가 오른쪽
            diff = pos - r;
            l += diff;
            r += diff;
        }
        result += diff;
    }
	cout << result;
}

 

🔗 코드 링크

🕧 결과