[구름LEVEL] 근묵자흑

난이도	정답률
★★	61.9%

구름LEVEL

문제

현재 1부터 N까지의 정수가 한 번씩 등장하는 길이 N의 수열이 있습니다. 여기서 당신은 연속된 K개의 정수를 골라서 한 곳에 잠시 모아둘 수 있습니다. 시간이 지나면 당신이 고른 K개의 정수들은 K개 중 가장 작은 정수가 됩니다. 이 시간은 고려하지 않습니다. 여기서 이 수열을 모두 같은 수로 만들고자 할 때 최소 몇 번 골라야 하는지 구해주세요.

해결

key point, 길이가 N인 수열을 최소한으로 겹치게 K개씩 묶는다.

1. 1부터 시작하여 N까지 k만큼 움직인다.
2. 이때 중요한 것은 처음에만 k만큼 움직이고 그 이후부터는 바로 직전에 골랐던 k개의 정수 중 마지막 숫자부터 k-1개의 숫자를 합하여 k개가되어야 한다.
3. 위처럼 묶을 수 있다면 ans변수를 +1 해주고
4. 현재 보고있는 위치가 수열의 크기를 넘어섰다면 반복문을 종료한다.

이렇게 N까지의 수열을, 바로 직전에 골랐던 K를 포함하여 K개씩 고른 횟수를 저장하여 출력하면 모두 같은 수로 만들고자하는 최소 횟수가 된다. 

코드

#include <iostream>
#include <algorithm>
using namespace std;
int input[100000];
int n, k, ans;
int main() {
    scanf("%d %d", &n, &k);
    
    for (int i = 1; i <= n; i++) {
        scanf("%d", &input[i]);
    }
    int idx = 1;
    while (1) {
        if (idx > n)break;
        if (idx == 1) idx += k;
        else idx += k-1;
        ans += 1;        
    }
    printf("%d", ans);
    return 0;
}