[C] 백준 2994번 : 내한 공연

 

오늘은 knapsack 문제를 풀어보았습니다  •'-'•)و✧ 

저는 재귀 함수 없이 배열로 DP 문제를 푸는 게 익숙지 않아서, 이 문제를 푸는 데 꽤나 고민을 오래 했습니다ㅜ

DP 문제 정말 싫어요..

.

이번에도 이 3가지 단계를 거쳐 문제를 풀어보았습니다!

1. 어떤 방식으로 해결할지 고민하기

2. 임의의 숫자를 대입하여 직접 풀어보기

3. 일반화해서 코드로 작성하기

 

백준 2994번

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

2994번: 내한 공연

 

1. 어떤 방식으로 해결할지 고민하기

이 문제는 우선 0/1 knapsack 문제입니다. (한번 쉬면 본인 쉬는 시간이 끝날 때까지 계속 쉼! 쪼개기 불가능)

따라서 Dynamic Programming으로 해결을 해야 하는데, 멤버의 수(N)가 최대 500명까지 있을 수 있기 때문에 재귀 호출로는 풀 수 없음을 알 수 있습니다.

또한 일반적인 knapsack 문제와는 다르게, 한 번에 1명씩 담는 게 (쉬는 게) 아니라 2명까지도 동시에 담을 수 있습니다.

저는 이것을 어떻게 구현하면 좋을까 고민을 하다가, 그냥 배낭을 2개라고 생각하기로 하였습니다.

즉 크기가 T인 배낭을 2개 준비하고, T를 넘지 않는 선에서 N명을 담는 것입니다.

 

-------------------------------------------------------------------------------------------------------------------

 

2. 임의의 숫자를 대입하여 직접 풀어보기

 

2994번 예제

 

주어진 예제를 대입해서 풀어보았을 때는 별 다른 문제를 느끼지 못하였는데,

다른 예제를 사용해보니 문제가 좀 더 복잡게 느껴졌습니다.

 

2994번 예제2

 

예제 1에는 배낭에 물건을 담는 순서가 중요하지 않았습니다.

하지만 예제 2에서, 주어진 입력을 index 순으로 담는다면 배낭이 넘쳐서 되돌아가야 하는 경우가 발생합니다.

(ex. 순서대로 배낭 1에 1과 2를 담아버린 경우 -> 남은 2와 3을 배낭 2에 담을 수 없음, 넘침)

만약 배낭이 1개라면 쉽게 되돌아갈 수 있겠지만, 배낭이 2개라고 생각하니 조금 복잡게 느껴졌습니다.

따라서 저는 visited 배열을 별도로 더 선언하여 각 index를 담았으면 1, 안 담았으면 0과 같은 방식으로 구분을 지었습니다. (배낭이 터졌을 때 되돌아가기 쉽게 하기 위해)

 

의사코드

 

이것은 제가 문제를 고민하면서 대충 작성해본 의사 코드입니다.

코드를 작성하면서 조건을 조금 더 추가하기는 하였지만, 큰 틀은 대충 이러합니다!

 

-------------------------------------------------------------------------------------------------------------------

 

3. 일반화해서 코드로 작성하기

 

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>

int rest[3][10000];
int visited[3][10000];

int main() {

	int T, N;
	scanf("%d%d", &T, &N);
	int member[10000];
	int result[10000];

	// 입력
	for (int i = 1; i <= N; i++)
		scanf("%d", &member[i]);

	int cnt;
	for (int i = 1; i <= N; i++) {
		cnt = 0;
		for (int j = 1; j <= 2; j++) {
			if (visited[j][i] != 0) {
				visited[j][i] = 0;
				rest[j][i] = rest[j][i - 1];
			}
			else
			{
				if (cnt==0 && (rest[j][i - 1] + member[i] <= T)) {
					rest[j][i] = rest[j][i - 1] + member[i];
					visited[j][i] = 1;
					cnt++;
				}
				else
					rest[j][i] = rest[j][i-1];
			}
		}
		if (cnt == 0)
			i-=2;
	}

	// 결과
	for (int i = 1; i <= 2; i++) {
		for (int j = 1; j <= N; j++) {
			if (visited[i][j] == 1) {
				result[j] = rest[i][j-1];
			}
		}
	}

	for (int i = 1; i <= N; i++)
		printf("%d ", result[i]);

	return 0;
}

 

입력은 member 배열을, 출력은 result 배열을 사용하였습니다.

rest 배열에는 누적 쉬는 시간을 저장하였고, 배낭이 2개이기 때문에 2차원 배열을 사용하였습니다!

visited 배열은 앞서 언급했던 바와 같이 물건이(쉬는 시간이?) 담겨있는지 여부를 확인하는 배열입니다.

.

추가적으로 의사 코드에서 미처 생각하지 못했던 부분이 있었습니다.

그것은 바로 rest 배열이 쉬는 시간을 누적해서 저장하기 때문에,

index가 증가할 때마다 누적 값 또한 계속 담아주어야 합니다.

따라서 안쪽 for문 안의 else 문에 조건을 하나 더 추가해주었습니다.

-> rest [j][i] = rest [j][i-1]

.

마지막으로 출력은 visited 배열을 참고하여 visited 값이 1인 것만을 담아주었습니다.

(누적 값이기 때문에 이전 index의 rest 값을 참고하면 쉽게 구할 수 있음!)

 

-------------------------------------------------------------------------------------------------------------------

 

+) 처음에 문제를  풀고 코드를 제출하였는데,,

제출하는 종종 런타임 에러 가 나와서 꽤나 골머리를 앓았습니다..^^

알고 보니 rest 배열과 visited 배열의 범위를 잘못 설정했었더라고요...ㅎ

다들 index를 1부터 사용할 때는 배열 크기를 꼭 조심하세요..^^

1 더해주는 거 잊지 말기,, (심한 욕..)