글 읽기 - C++ 2212센서 백트래킹에 대해서

blou888 1년 전 0

저는 백트래킹으로

구간의 끝점을 담아서
그 앞에 있는 인덱스의 값 차이를 구해서 그 총합이 가장 짧은 것으로 초기화를 하였습니다.

하지만 끝점을 찾을 때, 저는 백트래킹을 사용했는데,

이 풀이로 하면 시간초과가 나나요??

아니면, 제가 어딘가를 놓치고 있는 부분이 있는걸까요??

혹시, 구간을 좀 더 효율적으로 구분 할 수 있는 방법이 있을까요?

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

int N, K;
vector<int> V;
vector<int> arr;


int ans = 987654321;
void findMin(int deep, int idx) {
	if (deep == K) {
		int sum = 0;
		
		//첫번째 값에서 0까지 차이 구해주기,
		sum += abs(arr[V[0]] - arr[0]);
		
		if (K == 1) {
			//K가 1일 땐 우측도 구해줘야 함.
			sum += abs(arr[N - 1] - arr[V[0]]);
			
		}
		for (int i = 1; i < K; i++) {
			//각 구역의 인덱스에서
			//앞의 나눈 인덱스 까지 차이를 구해주기.
			sum += abs(arr[V[i]] - arr[V[i - 1] + 1]);
			
			if (i + 1 == K) {
				//마지막 인덱스는 우측도 더해줘야 함.
				sum += abs(arr[arr.size() - 1] - arr[V[i]]);
			}
		}
		if (ans > sum) {
			ans = sum;
		}
	}
	else {
		for (int i = idx; i < arr.size(); i++) {
			V.push_back(i);
			findMin(deep + 1, i + 1);
			V.pop_back();
		}
	}
}

int main()
{
    ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	
	cin >> N >> K;
	int tc = N;
	for (int i = 0; i < tc; i++) {
		int val;
		cin >> val;
		
		arr.push_back(val);
	}
	
	sort(arr.begin(), arr.end());

	if (N > K) {
		findMin(0, 0);
		cout << ans << "\n";
	}
	else {
		cout << 0 << "\n";
	}
}

kokosoko59 1년 전 1

n,k가 커서 올리신 코드로는 시간초과가 생길 것 같습니다. 백트래킹 말고 더 효율적인 풀이가 있습니다. 그 풀이를 쓰면 정렬을 포함해서 n logn 의 시간복잡도로 풀 수 있습니다.

이 문제의 알고리즘 분류를 보면 힌트를 얻으실 수 있을겁니다.

blou888 1년 전 0

감사합니다! 조금 더 생각 해 보겠습니다..

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

C++ 2212센서 백트래킹에 대해서

blou888 1년 전 0

kokosoko59 1년 전 1

blou888 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말