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

 

1) 문제설명

 

백준 Online Judge 11497번 통나무 건너뛰기

 

백준 Online Judge 11497번 통나무 건너뛰기

 

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

11497번: 통나무 건너뛰기

 

2) 해결방법

 

입력값 중 가장 큰 값을 중앙에 두고 양옆으로 작아지게 수를 정렬한 후 앞뒤 값의 차이들 중 최댓값을 출력하면 된다.

13 10 12 11 10 11 12 -> 10 11 12 13 12 11 10으로 정렬 한 뒤

| 10 vs 11 | 11 vs 12 |... | 11 vs 10 | 앞뒤 차이들 중 최댓값을 출력한다.

입력값을 오름차순으로 정렬한 뒤

짝수 인덱스를 (0~n/2) 홀수의 인덱스를 (n/2~n)로 설정하여 새로운 배열을 만들었다.

이후 max를 통해 앞뒤 배열의 차의 최댓값을 출력하였다.

 

3) 코드

 

#include<iostream>
#include<queue>
#include<string.h>
#include<math.h>
#include<cmath>
#include<algorithm>

using namespace std;

int dp[1000001];
int n[10001], arr[1000][10001], brr[1000][10001];
/*
통나무 건너뛰기
해결방안
중앙이 최대가 되도록 정렬 한다
그 후 서로의 차이의 최대값을 출력한다.

*/
bool compare(int a, int b) {
	return a > b;
}

int main() {
	
	int t;	
	cin >> t;
	for (int i = 0; i < t; i++) {
		cin >> n[i];		
		for (int j = 0; j < n[i]; j++) {
			cin >> arr[i][j];
		}
		sort(arr[i], arr[i] + n[i]);
	}
	
	for (int i = 0; i < t; i++) {
		int cnt = 1;
		for (int j = 0; j < n[i]; j++) {
			if (j % 2 == 0) {
				brr[i][j/2] = arr[i][j]; //짝수의 인덱스를 0 ~ n/2 까지
			}
		}
		for (int j = 1; j < n[i]; j++) {
			if (j % 2 == 1) {
				brr[i][n[i] - cnt] = arr[i][j]; // 홀수의 인덱스를 n/2 ~ n 까지
				cnt++;
			}
		}
		
	}

	int maxt;
	for (int i = 0; i < t; i++) {
		maxt = 0;
		for (int j = 0; j < n[i]; j++) {
			if (j + 1 < n[i]) {
				if (brr[i][j + 1] > brr[i][j]) {
					maxt = max(brr[i][j + 1] - brr[i][j], maxt);
				}
				else if (brr[i][j] > brr[i][j + 1]) {
					maxt = max(brr[i][j] - brr[i][j + 1], maxt);
				}
			}
			
			
		}
		cout << maxt << endl;
	}
		
}
// 2 4 5 7 9 -> 2 5 9 7 4  0  1  2  3  4  5  6
// 10 10 11 11 12 12 13 -> 10 11 12 13 12 11 10
//  0  1  2  3  4  5  6    0  2  4  6  5  3  1

큰 값을 중앙에 두고 양옆으로 작아지게 하는 정렬을 구현하는데 오래걸렸다.