[백준 BOJ] 11497번 통나무 건너뛰기 (C++/cpp)

문제 설명

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

 

 

접근 방법 - 그리디 알고리즘을 활용한 정렬 문제

백준의 11497번 문제는 그리디 알고리즘과 정렬을 활용하여 해결해야 하는 문제이다.

해당 문제는, 입력으로 주어지는 높이들의 통나무를 임의로 배치하여 인접한 것들끼리 건너뛸 때 나타날 수 있는 난이도 값의 최솟값을 구하여 출력해야 하는 문제이다.

이때 난이도 값은, 통나무들을 임의로 배치하였을 때 인접한 통나무 간 높이의 차의 최댓값으로 결정이 난다.

(통나무를 배열 형태로 나열하였을 때, 배열의 시작과 끝에 있는 통나무도 서로 인접해 있다는 점을 주의해야 한다.)

 

필자는 문제 지문을 읽으면서, "그렇다면 서서히 높아지고 서서히 낮아지도록 배치하면 정답을 구할 수 있지 않을까?"라는 생각에서 문제 해결을 시도해 보았다.

그 결과, 배열과 정렬을 통하여 그리디(?)하게 해결할 수 있는 방법을 찾아내었다.

예제 입출력 중 2번째 테스트 케이스를 구상한 로직에 적용하여 아래에 설명을 기재해 놓으니, 함께 참고하면 도움이 될 것이다.

n=5, [2, 4, 5, 7, 9] 입력

(로직의 흐름)
- 가장 큰 값인 9를, 그다음으로 큰 값인 7, 5에 연결
- 7, 5는 그다음으로 큰 값인 4, 2에 각각 연결
=> [2, 5, 9, 7, 4]
이렇게 하면, 통나무 간의 높이차가 각각 3, 4, 2, 3, 2가 된다.
이 경우에서 정답은 4가 나와야 한다.

(로직 구현)
(1) 내림차순으로 정렬
[9, 7, 5, 4, 2]

(2) 가장 앞에 있는 값은 1번, 2번 값과 연결 & 높이차 구하기
* 9 - 7 = 2
* 9 - 5 = 4
현재까지의 난이도 값 :: 4

(3) 그 이후로의 값은, 그다음으로 큰 값끼리 연결 & 높이차 구하기
* 7 - 4 = 3
* 5 - 2 = 3
현재까지의 난이도 값 :: 4

(4) 정답 :: 4 

 

필자는 위로 작성한 로직을 기반으로 코드를 작성하여 문제를 해결해 보았다.

혹여나 해당 문제를 해결하는 데에 어려움을 겪고 있다면, 아래의 설명과 코드를 참고해 보길 바란다.

필자는 아래의 순서대로 코드를 작성하여 문제를 해결하였다.

 

코드의 실행 순서

1) 테스트 케이스의 수(t)를 입력받는다.

 

2) t의 크기만큼, 반복문을 수행하여 아래의 연산을 취한다.

- 통나무의 개수(n)를 입력받는다.

- 통나무의 높이를 저장할 벡터 v를 선언해 두고, 통나무의 높이들을 순차적으로 입력받아 v에 삽입하도록 한다.

- sort() 함수로 v 요소값들을 정렬한다. 이때, compare 함수를 별도로 선언하여 내림차순 정렬을 수행하도록 한다.

- 아래의 절차를 수행하여, 정답을 구하도록 한다.

- 통나무 간의 간격 차 중 가장 큰 값을 저장할 변수 max를 0으로 초기화하여 선언해 둔다. 
- v[0](가장 큰 통나무 높이)를 v[1], v[2](다음으로 큰 두 통나무 높이)와 연결하여, 이 두 간격 중 큰 값을 max 값으로 저장하도록 한다.
- 다른 반복문을 통해 내림차순 정렬된 v에 대해 2칸씩 떨어진 통나무끼리 연결하여, 이 간격의 크기가 max보다 크다면 max를 해당 값으로 갱신하도록 한다.

 

3) 2)에서 연산이 완료되었다면, 최종적으로 저장된 max 값을 정답으로 출력한 뒤 실행 종료한다.

반응형

 

성공한 코드

#define _CRT_SECURE_NO_WARNINGS
#pragma warning(disable: 4996)
#include <iostream>
#include <vector>
#include <algorithm>
#define endl '\n'
using namespace std;

//백준 11497번 코드
int t, n, num;
bool compare(int a, int b) {
    return a > b;
}

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

    cin >> t;
    for (int i = 0; i < t; i++) {
        cin >> n;
        vector<int> v;
        for (int j = 0; j < n; j++) {
            cin >> num;
            v.push_back(num);
        }
        sort(v.begin(), v.end(), compare);
        
        int max = 0;
        if (max < v[0] - v[1]) { max = v[0] - v[1]; }
        if (max < v[0] - v[2]) { max = v[0] - v[2]; }
        for (int j = 1; j < n - 2; j++) {
            int tmp = v[j] - v[j + 2];
            if (max < tmp) { max = tmp; }
        }

        cout << max << endl;
    }
}

 

제출 결과

(2024.04.07 백준 11497번 문제 제출 결과)