[Week 5] PACKING self review - Scaachan

[Queue-ri]

PACKING self review

• 파일명: PACKING/Scaachan.cpp
• 수행시간: 16ms

1. 문제 해결 과정

일단, 입출력 조건이 많아서 물건을 하나의 Element 구조체로 구현했습니다.

로직은 매번 해당 물건을 선택할 것인지, 안 할 것인지의 2가지 분기로 나누어 둘 중 최대 절박도인 것을 선택하려 했습니다.

하지만 해당 로직으로 최대 절박도는 쉽게 구할 수 있는 반면 packing할 물건을 vector에 담는 데에는 어려움이 있었습니다.

구현은 가능하나 vector에 원소 삽입/삭제를 반복하는 것은 많은 오버헤드를 초래하고
heap에서 string 컨테이너의 할당/해제를 반복하는 방식은 비효율적이어서 문제의 의도가 아닐 것이라 판단했습니다.

따라서 어떤 물건을 담을지 선택하여 vector에 넣는 부분은 책을 참고하였고, 제 코드에 맞게 살짝 수정했습니다.

2. 아이디어

dp로 풀었습니다.

특이사항이라면 '최대 절박도 계산', '물건 선택' 두 가지를 따로 나누어 2개의 재귀함수를 작성했습니다.

3. 코드 설명

typedef struct _Element {
	string name;
	int weight;
	int priority;
}Element;

물건의 정보를 묶어둔 Element 구조체입니다.

int calc(int e, int wsum) {
	if (e >= N) return 0;
	int& cache = memo[e][wsum];
	if (~cache) return cache;

	cache = calc(e + 1, wsum); // not packing e
	if (wsum + v[e].weight <= W) // packing e
		cache = max(cache, calc(e + 1, wsum + v[e].weight) + v[e].priority);

	return cache;
}

최대 절박도를 계산하는 calc() 함수입니다.

물건 e를 pack하지 않는 경우와 pack 하는 경우를 서로 비교하여 더 높은 절박도를 캐싱합니다.

참고로, 기존 풀이들은 W(최대 용량)에서 weight(물건 부피)를 빼면서 호출해나가는데,

저는 반대로 부피를 더해나가면서 W를 초과하지 않는지 검사했습니다.

void track(int e, int wsum) {
	if (e >= N) return;
	if (calc(e, wsum) == calc(e + 1, wsum)) // e was not packed
		track(e + 1, wsum);
	else { // e was packed
		ans.push_back(v[e].name);
		track(e + 1, wsum + v[e].weight);
	}
}

track()은 calc()가 계산한 절박도에 따라 물건 e를 챙겼는지 안챙겼는지 판별하는 함수입니다.

calc()가 캐싱을 하고 있기에 두 재귀함수를 중첩해도 수행시간이 크게 늘어나지 않습니다.

이 부분은 글로 설명하면 별로라서 시간 될 때 트리 형태의 스택 트레이스를 그려서 설명해보겠습니다.