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

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

11497번: 통나무 건너뛰기

 

아이디어의 흐름

1. 시간복잡도 고려

입력이 10,000개, 시간제한은 1초이므로 O(n^2) 알고리즘이어도 시간 안에 통과할 것이라 예상

2. 아이디어 구상

임의로 수를 입력해주었을 때, 인접한 두 수의 차의 절대값이 최소가 되어야한다.이 통나무는 원형으로 배치되므로, 오름/내림차순 정렬을 할 경우 양 끝단의 차가 가장 크게 나온다. 단순한 정렬은 아닐 것이라 생각, 추상적으로 생각해보았을 때 배열을 정렬한 후 배열의 원소를 새로운 배열의 양 끝으로 번갈아 저장하면 되겠다는 아이디어 구상.

1. 입력받은 배열을 오름차순 정렬
2. 배열의 처음부터 끝까지 순회하며, 새로운 배열의 양 끝으로 번갈아가며 수를 저장
3. 새롭게 만들어진 배열을 다시 순회하여 인접한 원소의 차의 최대값을 구하고자 함.

2-1. 초기 아이디어의 한계

정렬한 배열의 짝수항, 홀수항을 새롭게 만든 배열의 양 끝으로 번갈아 저장하도록 구현해야하는데, 그러기 위해서는 새로운 배열의 양 끝을 가리키고 있을 포인터 두 개를 계속 다뤄야한다. 큰 문제는 아니지만 '조금 더 번거롭지 않게 풀 수 있지 않을까' 하는 생각이 들었음.

3. 수정된 아이디어 

기존의 아이디어대로 정렬, 삽입까지 마친 후 답을 어떻게 구하는가 생각해보면, 결과적으로 답을 구하는 방법은 인접한 원소와의 차를 구한 뒤 최대값을 찾는 것이다. 그렇다면 굳이 새로운 배열을 만들 필요 없이, 새로운 배열에서 인접한 원소를 빼는 것처럼 기존의 정렬한 배열에서 i 번째 i + 2번째 원소, 즉 한 다리 건너 있는 원소의 차를 구해주면 그 값은 새로운 배열을 만든 후 인접한 원소의 차와 같게 된다.

1. 입력받은 배열을 오름차순 정렬
2. max 값을 저장할 변수 선언
3. 정렬된 배열을 처음부터 N - 2 까지 순회하며 현재 i번째 항과 i + 2 번째 항의 차가 max 값보다 큰지 작은지 결정
4. 문제의 조건대로 원형으로 통나무를 배치할 때 정렬된 배열의 0, 1 번째 항은 처음과 끝 지점, N - 1, N - 2 번째 항은 중간에 위치하지만, 위 순회를 통해 계산되지 않으므로 max값과 별도로 비교

4. 코드

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;	

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

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

		vector <int> v(N);

		for (int i = 0; i < N; i++) cin >> v[i];

		sort(v.begin(), v.end());

		int result = 0;
		result = max(result, v[1] - v[0]);
		result = max(result, v[N - 1] - v[N - 2]);

		for (int i = 0; i < N - 2; i++) {
			result = max(result, v[i + 2] - v[i]);
		}
		cout << result << '\n';
	}
}

5. 아쉬운 점

• 총 소요시간 : 66분
• 문제이해 : 5분
• 아이디어 구상 : 15분
• 구현 : 46분

초기 아이디어대로 구현을 하려고 할 때 생각대로 잘 구현이 되지 않았었다. 크게 시간이 지났다는 생각은 들지 않았는데 의외로 30분이라는 시간이 낭비되었다...그래서 이 방법을 포기하고 두 번째 아이디어를 구상하고, 이를 구현하기까지 고작 +16분이 더 걸려 구현에 46분이 걸리게 되었다. 처음부터 두 번째 아이디어를 떠올렸다면 약 30~40분 정도 걸릴 문제였는데, 절대 어려운 문제가 아님에도 구현력이 부족하여 30분을 낭비한 게 아쉬운 문제다.

아이디어 구상 단계에서부터 구현 감안하기, 구현력 더 키우기