[Lv3] 소프티어 택배 마스터 광우 C++ 백트래킹

리뷰

 

https://softeer.ai/practice/6273

Softeer - 현대자동차그룹 SW인재확보플랫폼

 

기본적인 백트래킹 문제, 커스텀 TC를 만들어 제출할 때 최악의 경우 시간초과가 날 줄 알았는데 너무 악랄한 예제는 주지 않는 듯 하다.

 

 

전역 변수

• n : 레일의 개수를 저장할 변수
• m : 바구니에 담을 수 있는 최대 무게를 저장할 변수
• k : 작업을 진행할 횟수를 저장할 변수
• lst : 각 레일의 전용 무게를 저장할 배열
• v : 레일 선택 시 방문 처리를 진행할 배열
• stack : 선택한 레일의 인덱스를 저장할 정수형 벡터

 

함수

1. bt

void bt(int level)

 

백트래킹을 통해 레일을 사용한 모든 경우의 수를 탐색하기 위한 함수

1. 매개 변수로 재귀 단계 level을 전달받는다.
2. 기저 조건으로 level이 n에 도달했을 경우 getSum함수를 호출해 ans의 값을 최소값으로 최신화 한 후 리턴한다.
3. 기저 조건에 해당하지 않는다면 n개의 레일 정보를 순회하는 for문을 개행한다.
4. 이미 stack에 넣어둔 레일이라면 continue 처리를 진행해 준다.
5. stack에 없는 레일이라면 방문처리 후 해당 레일의 인덱스를 stack에 추가해 준다.
6. 재귀 레벨을 증가시켜 bt함수를 수행하여 재귀를 이어서 진행해 준다.
7. 재귀를 빠져나온 경우 현재 선택했던 레일의 방문을 풀어주고 stack에서 꺼내어 준다.

 

2. getSum

int getSum()

 

현재 선택한 레일을 순서대로 배치하여 k번의 작업 시 쌓이는 택배의 무게를 구하는 함수

1. 진행한 일의 횟수 cnt, 현재 바구니의 무게 cur, 현재 레일의 인덱스 idx, 총 택배의 무게 sum을 모두 0으로 초기화한다.
2. cnt가 k보다 작을 경우 while 루프를 계속 수행해 준다.
3. 만약 cur + lst[stack[idx]]가 m이하라면 cur에 lst[stack[idx]]를 더해준다.
4. m보다 크다면 sum에 현재 cur을 더해주고, cnt를 1만큼 증가, cur에 lst[stack[idx]]값을 저장해 준다.
5. idx를 전위증가 시킨 값이 n이라면 idx를 다시 0으로 만들어 준다.
6. 만약 sum이 ans이상이라면 더 이상 탐색하지 않고 바로 리턴해 준다.
7. 위 기저조건에 해당하지 않는다면 while 루프가 종료된 후 sum에 저장된 값을 리턴해준다.

 

문제풀이

1. n, m, k값을 입력 받고, n개의 레일 정보를 lst에 저장해 준다.
2. bt함수에 매개변수로 0을 전달해 준 뒤 백트래킹을 수행해 준다.
3. ans에 저장된 값을 출력해 준다.

 

트러블 슈팅

없음

 

 

참고 사항

제약조건
3 ≤ N ≤ 10
max(Ni) < M ≤ 50
1 ≤ K ≤ 50
1 ≤ Ni ≤ 50

N의 크기가 작으므로 백트래킹을 수행해도 문제가 없을 것이라고 생각했다.

그러나 커스텀 TC를 만들어 돌려봤을땐 상당한 시간이 걸리길래 정답이 아닌가 생각했다.

10 50 50 
1 1 1 1 1 1 1 1 1 1

 

위 예제는 제약조건에 포함된다, 해당 예제를 돌렸을 시 시간이 매우 많이 소요되었다.

그냥 일단 제출해 봤더니 AC는 맞았는데 위 예제와 같은 엣지 케이스는 존재하지 않는 것 같다.

 

정답 코드

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

int n, m, k, ans = 2e9;
int lst[10];
bool v[10];
vector<int> stack;

int getSum() {
	int cnt = 0;
	int cur = 0;
	int idx = 0;
	int sum = 0;
	while (cnt < k) {
		if (cur + lst[stack[idx]] <= m) cur += lst[stack[idx]];
		else {
			sum += cur;
			cnt++;
			cur = lst[stack[idx]];
		}
		if (++idx == n) idx = 0;
		if (sum >= ans) return 2e9;
	}
	return sum;
}

void bt(int level) {
	if (level == n) {
		ans = min(ans, getSum());
		return;
	}

	for (int i = 0; i < n; ++i) {
		if (v[i]) continue;
		v[i] = 1;
		stack.push_back(i);
		bt(level + 1);
		v[i] = 0;
		stack.pop_back();
	}
}

int main() {
	cin >> n >> m >> k;
	for (int i = 0; i < n; ++i) cin >> lst[i];
	bt(0);
	cout << ans;
}