백준 11497 통나무 건너뛰기 (C++)

안유태·2023년 11월 9일
0

알고리즘

목록 보기
175/239

11497번: 통나무 건너뛰기

그리디를 이용한 문제이다. 문제를 읽어보면 배열의 첫 값과 마지막 값은 연결이 되어있다. 이 상태에서 최대 난이도가 최소인 경우를 찾아야 한다. 즉 배열을 정렬을 해줄 때 가운데에 가장 큰 값을 두고 양 옆으로 점점 작아지는 피라미드 형태로 정렬을 해주어야 한다. 피라미드 형태로 정렬을 해주는 방법은 먼저 오름차순으로 정렬을 해주고 첫 값은 왼쪽, 다음 값은 오른쪽, 또 다음 값은 왼쪽으로 값을 저장을 해주게 되면 최대 난이도가 최소인 피라미드 형태의 배열을 찾을 수 있다. 코드를 보면 첫 값과 끝 값은 연결되어 있으므로 차이를 먼저 구해 result에 저장을 해준다. 그리고 반복문을 돌며 최댓값을 구해주고 출력을 해주었다. 쉽게 풀 수 있었던 문제였다.



#include <iostream>
#include <algorithm>

using namespace std;

int N;
int L[10000];

void solution() {
    sort(L, L + N);

    int result = L[1] - L[0];

    for (int i = 2; i < N; i+=2) {
        result = max(result, L[i] - L[i - 2]);
    }
    for (int i = 3; i < N; i += 2) {
        result = max(result, L[i] - L[i - 2]);
    }

    cout << result << "\n";
}

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

    int T;
    cin >> T;
    while (T--) {
        cin >> N;

        for (int i = 0; i < N; i++) {
            cin >> L[i];
        }

        solution();
    }



    return 0;
}
profile
공부하는 개발자

0개의 댓글