[C++] 11497번 통나무 건너뛰기

풀이

11497번 문제보기

 

코드 1 (vector 사용)

#include <iostream>
#include <algorithm>
//#include <cstdlib> 없어도 정답이 나옴
#include <vector>

int main(){
    int T;
    std::cin>>T;

    // 테스트 케이스만큼 반복
    for(int _case=0; _case<T; _case++){
        int n;
        std::cin>>n;
        int half = n/2;
        std::vector<int> arr(n, 0);
        std::vector<int> ansArr(n, 0);

        for(int i=0; i<n; i++) std::cin>>arr[i];
        int j=n-1;

        // 주어진 배열을 크기 순으로 정렬
        std::sort(arr.begin(), arr.end());

        // 가장 큰 숫자는 배열 중앙으로
        ansArr[half] = arr[j];

        for(int i=1; i<=half; i++){
            j--;
            if(j<0) break;
            ansArr[half-i] = arr[j];
            j--;
            if(j<0) break;
            ansArr[half+i] = arr[j];
        }

        int answer=0;
        for(int i=0; i<n-1; i++){
            int gap = abs(ansArr[i]-ansArr[i+1]);
            answer = std::max(answer, gap);
        }
        std::cout<<answer<<'\n';
    }

    return 0;
}

 

제출코드 2 (new delete를 사용한 동적할당)

#include <iostream>
#include <algorithm>
#include <cstdlib>

int main(){
    int T;
    std::cin>>T;

    // 테스트 케이스만큼 반복
    for(int _case=0; _case<T; _case++){
        int n;
        std::cin>>n;
        int half = n/2;
        int *arr = new int[n];
        int *ansArr = new int[n];
        
        for(int i=0; i<n; i++) std::cin>>arr[i];
        int j=n-1;

        // 주어진 배열을 크기 순으로 정렬
        std::sort(arr, arr+n);

        // 가장 큰 숫자는 배열 중앙으로
        ansArr[half] = arr[j];

        // 최소 난이도가 나오도록 통나무 배치
        for(int i=1; i<=half; i++){
            j--;
            if(j<0) break;
            ansArr[half-i] = arr[j];
            j--;
            if(j<0) break;
            ansArr[half+i] = arr[j];
        }

        // 최소 난이도 출력
        int answer=0;
        for(int i=0; i<n-1; i++){
            int gap = abs(ansArr[i]-ansArr[i+1]);
            answer = std::max(answer, gap);
        }
        std::cout<<answer<<'\n';

        delete[] arr;
        delete[] ansArr;
    }
    return 0;
}

풀이

가장 큰 값이 가장 가운데로 오도록 하고 그 다음 큰 수들을 차례대로 가운데 옆으로 배치시켰다.

 

후기

항상 vector만 사용했었는데 이번에 다른 방법으로도 사용해봤다.