[알고리즘] 백준 2828

백준 2828번 사과 담기 게임

해결 과정 요약

사과를 받기위해 바구니를 최소한으로 움직여주고 바구니의 총 이동거리를 구하면 된다.
사과가 떨어지는 순서가 정해져있고 모든 사과를 받아야하므로 최종해는 부분문제에 대한 최적해로 구성된다고 볼 수 있다. 따라서 당장 눈앞에 있는 사과만 계속 받아내면 정답에 도달하게 되는 그리디 알고리즘 문제다.
바구니를 옮기면서 cnt값을 늘려주고 사과를 받아냈다면 ret값에 cnt값을 더해준 후 cnt를 0으로 초기화한다.
위 방식으로 사과를 모두 받아내면 종료한다.

풀이

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

int first,last,N,M,J,apple,ret;

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

    cin >> N >> M >> J;
    first = 1; last = M;
    for (int i=0; i<J; i++){
        cin >> apple;
        int cnt = 0;
        for(int j=0; j<N-M; j++){
            if(first <= apple && apple <= last) continue;
            else if(apple < first) { cnt++; first--; last--; }
            else if(last < apple) { cnt++; first++; last++; }
        }
        ret += cnt;
    }
    cout << ret;
    return 0;
}

코멘트

for문을 돌면서 바구니를 1칸씩 옮기는 방식을 쓰지 않고 계산으로 풀 수도 있을듯