[알고리즘 문제풀이] 기타 코딩테스트 1-3

문제 :

땅콩 먹기
A씨는 N 개의 땅콩을 발견했다. 땅콩은 1차원 수직선 위에 존재하고, i번째 땅콩은 원점으로부터 i 만큼 떨어져 있으며 A씨는 원점으로부터 e 만큼 떨어져 있는 곳에 있다. A씨는 땅콩을 먹는 것을 아주 좋아하지만, 모든 땅콩 중에서 M 개만을 먹을 수 있다.

 

A씨는 기억력이 좋지 않아 지금까지 지나온 길에 빨간 선을 그리는 마법을 부려왔다. 물론 이 수직선에서도 마찬가지이다. 즉, A씨가 수직선 위의 위치 3에서 위치 5까지 움직인다면, 위치 3에서 위치 5까지 총 길이 2의 빨간 선이 그려진다. 단, 이미 빨간 선이 칠해진 곳을 다시 이동하게 될 경우, 새롭게 빨간 선이 그려지지는 않는다.
A씨가 N 개의 땅콩 중 M 개의 땅콩을 먹으려 할 때, 그려지게 될 빨간 선 중 최소 길이를 출력하시오.

 

 

 

입력 :

첫 번째 줄에 땅콩의 개수 N, 먹으려는 땅콩 개수 M, 그리고 소마의 위치 E 순으로 공백을 구분자로 입력받는다. (N, M 그리고 E는 정수이다.)
1 ≦ N ≦ 10,000
1 ≦ M ≦ N
두 번째 줄에 N개의 숫자에 대하여 땅콩이 있는 위치를 공백을 구분자로 입력받는다. (땅콩의 위치는 정수이다.)
두 개의 땅콩이 같은 위치에 있는 예시는 입력되지 않으며 땅콩의 위치는 오름차순으로 입력된다.
소마의 위치와 땅콩의 위치가 겹치는 경우 소마는 움직이지 않고 땅콩을 바로 먹을 수 있다.

 

ex)
6 3 7
2 4 5 8 11 12

 

 

 

출력 :

A씨가 땅콩을 먹으려 할 때 그려지게 될 빨간 선 중 최소 길이를 출력한다.

ex)

4

 

 

 

풀이 및 코드 :

#define INF 987654321;
#include <iostream>
#include <vector>
using namespace std;
const int MAX = 10001;

int N, M, E;
vector <int> v;
int minvalue = INF;

int solution() {
    int pointer = 0;
    while (pointer != N - M + 1) { //볼필요없는 부분까지 포인터가 가면 스탑
        int val1 = v[pointer + M - 1] - v[pointer]; //먹었을 때 빨간선의 길이
        if (E < v[pointer]) {
            val1 = val1 + v[pointer] - E;
        }
        else if (E > v[pointer+M-1]) {
            val1 = val1 + E - v[pointer + M - 1];
        }
        //여기까지 해서 값을 저장해줄 수 있다.
        if (minvalue >= val1) {
            minvalue = val1; //최대값을 갱신한다.
        }
        pointer++; //다음 포인터로 이동시킨다.
    }
    return minvalue;
}

int main(){
    cin >> N >> M >> E;
    int t;
    for (int i = 0; i < N; i++) {
        cin >> t;
        v.push_back(t);
    }
    cout << solution() << endl;
    return 0;
}