투자게임, 문제해결 훈련, 역방향 탐색

문제

투자게임을 하여 최대의 수익을 내려고 한다. N번의 투자기회가 있다. 각 기회마다 투자시기에 따른 기대수익이 있다. 투자기대 수익은 P이며, 투자시기는 T이다. 각각의 기회에 투자시기를 잘 조정하여 투자결정을 하면 최대의 수익을 낼 수 있다고 한다. 투자시기는 1부터 P값까지이다.

 

예를 들어 아래의 투자기회가 있다고 하자. N은 5이며 P와 T값은 아래와 같다.

투자시기가 1부터 4까지 있으며 최대 기대수익을 이룰 수 있는 투자시기 조정은 아래와 같다.

투자시기 4에는 투자기회 3번을, 투자시기 3에는 투자기회 4번을, 2시기에는 2번을, 1시기에는 0번이 오게 투자결정을 해야하며 이때의 기대수익은 35이다.

투자기회 N번과, 각각의 P, T가 주어질때 최대 투자기대수익의 값을 구해보자.

 

입력

투자시기 N은 1이상 10000이하임

기대수익 P는 1이상 1000이하임

투자시기 T는 1이상 10000이하임

 

case1

5
8 1
7 2
8 3
10 4
9 4

 

case2

4

10 3

7 5

8 1

2 1

 

출력

case1

35

 

case2

25

---

문제해결

순차적으로 투자 결정을 하게 되면 앞선 투자시기에서 결정한 값이 최선의 선택이 아닐 수 있다. 때문에 더 나은 투자기회가 발견될 시에 앞서 결정한 투자시기를 다시 번복해야한다. 따라서 정방향으로 순차적으로 투자결정을 하는 것은 비효율적이다.

역방향은 어떨까? 역방향으로 투자 결정을 하는 것이다. 역방향으로 최선의 결과를 선택하면서 투자결정을 해오면 다시 번복할 일도 없다. 그러기 위해선 아래의 규칙을 따라야한다.

1. 가장 큰 T값부터 역방향으로 결정해와야하기 때문에 maxT값을 알아낸다.

2. 역방향 T값부터 감소해가며 각투자 기회에 따른 P값이 가장 큰 투자번호를 선택한다.

3. 선택한 번호는 표시해두며 선택때마다 P값을 더한다.

 

투자결정의 조건은 아래와 같다.

1. 한번 선택한 투자기회는 다시 사용될 수 없다. used배열 사용

2. 각 투자 기회의 T값은 투자결정시기의 값 보다 같거나 커야한다.

3. T값이 가능하더라도 P값이 가장 큰 투자 기회를 선택한다.

 

이정도의 아이디어를 도출 할 수 있다. 사실 문제를 읽자마자 이렇게 아이디어를 도출하는 것은 여간 쉬운 것이 아닌 것 같다. 많은 훈련과 경험치가 쌓여야 제한된 시간내에 올바른 아이디어를 도출하고 문제해결을 할 수 있을 것 같다.

 

#include <stdio.h>

int N;
int P[10000+100];
int T[10000+100];
int used[10000+100];
int cost;


void Input(){
	scanf("%d", &N);
	for(int i=0; i<N; i++)
	{
		scanf("%d %d", &P[i], &T[i]);
	}
}

int Solve(){
	int i;
	int sum=0;
	int t;
	int selidx =0;
	int maxv =0;
	
	for(i=0; i<N; i++)
	{
		if(maxv < T[i]) maxv = T[i];
	}
	
	for(t = maxv; t>0; t--)
	{
		maxv=0;
		for(i=0; i<N; i++)
		{
			if(used[i])continue;
			if(t>T[i])continue;
			if(maxv>P[i])continue;
			maxv=P[i];
			selidx=i;
		}
		if(maxv==0) continue;
		sum+=maxv; used[selidx]=1;
	}	
	
	return sum;
}


int main() {
	Input();
	
	printf("%d",Solve());
	
	return 0;
}