[백준] 1083번: 소트

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

sort는 연속한 숫자끼리 숫자를 바꿀 수 있다.
처음에 접근할 때는 문제를 제대로 안 봐 sort가 완벽하게 될 때까지 바꾸는 줄 알았는데 sort할 수 있는 횟수와 결과값이 가장 큰 경우(사전에서 가장 뒤에 있는 경우)가 있다는 걸 알고 다시 코드를 짰다.
사전에서 가장 뒤에 있는 경우는 가장 앞에 있는 숫자가 가장 큰 경우이다. 하지만 우리는 sort할 수 있는 횟수가 정해져있다. 이를 유의해 나는 문제를 풀었다.

우선 첫번째에 배열(arr)의 값은 저렇고, 움직일 수 있는 횟수는 4만큼 주어져 있다고 하자. 그렇다면 arr[0] ~ arr[4]중에서 가장 큰 값의 index를 구하면 arr[2] = 10이 된다. 이 값이 arr[0]로 움직이려면 2번 움직여야 한다. 우리는 여전히 2번 더 움직일 수 있다.
다음 배열로 넘어갔을 때 우리는 arr[1] ~ arr[3] 중에서 가장 큰 값의 index를 구할 수 있다. 바로 arr[3] = 8로 이를 arr[1]로 옮기면 2번만큼 움직여 3번과 같이 sort될 수 있음을 알 수 있다.

이를 일반화 하면 arr[index] ~ arr[index + 움직일 수 있는 횟수]중에서 가장 큰 값의 index를 구해 움직일 수 있는 횟수 -= 가장 큰 값의 index를 한다. 이를 움직일 수 없을 때까지(움직일 수 있는 횟수 == 0) 움직이게 되면 사전에서 가장 뒤에 있는 경우가 된다.

#include <cstdio>

int arr[50] = {0, };
int N;

int findmax(int i, int S){
    int limit = S + i;
    int maxi, maxnum;
    if(N - 1 < S + i)
        limit = N-1;
    maxi = i;
    maxnum = 0;
    for(int j = i; j<= limit; j++){
        if(arr[j] > maxnum){
            maxi = j;
            maxnum = arr[j];
        }
    }

    for(int j = maxi; j > i; j--){
        maxnum = arr[j];
        arr[j] = arr[j-1];
        arr[j-1] = maxnum;
    }
    
    return S - maxi + i;
}
//

int main(int argc, const char * argv[]) {
    int S, num, i;
    scanf("%d", &N);
    for(i = 0; i<N; i++){
        scanf("%d", &arr[i]);
    }
    scanf("%d", &S);
    num = S;
    i = 0;
    while(num > 0 && i < N){
        num = findmax(i, num);
        i++;
    }
    for(i = 0; i<N; i++)
        printf("%d ", arr[i]);
    printf("\n");
}

나는 처음에 대충 풀어서 한번, 배열의 범위를 잘못 지정해 한번 틀렸다. 해당 문제는 배열의 범위를 넘어서더라도 오류를 내놓지 않았다.(틀렸습니다라고 출력)
문제를 똑바로 읽는 습관을 들이고, 실수를 하지않도록 신경 써야할 것 같다.