문제

가장 먼저 시작하는 회의부터 선택 할 경우 아래와 같이 늦게 시작하는 회의가 더 짧을 수 있는 경우의 반례가 존재하므로 최적의 답을 구할 수 없다. 원래 탐욕법으로는 최적을 구하기 보다 최적에 가까운 답을 구하는게 보통이지만 이 문제는 최적의 답(또는 최적의 답 중 하나)을 구할 수 있기 때문에 이 방법을 사용하여 답을 구할 수 없다.

가장 짧은 회의부터 선택할 경우에는 아래와 같이 먼저 시작하고 회의 시간이 더 긴 회의를 시작할 경우 더 많은 회의를 선택할 수 있는 경우가 존재하기 때문에 최적의 답을 구할 수 없다.

코드 상에서 위 방법들에 대한 반례에 대해 처리한다고 해도 결국 다른 반례가 나오기 때문에 위 방법들로는 해결할 수가 없다.

이 문제를 해결하는 방법은 가장 빨리 끝나는 회의부터 선택하는 것인데 가장 빨리 끝나는 회의를 선택할수록 그 뒤에 선택할 수 있는 회의시간이 늘어나기 때문에 어떤 경우라도 가장 많이 선택할 수 있다.

코드는 아래와 같이 짰다. 회의의 시작시간과 종료 시간을 가지고 있는 meeting 구조체를 만들고(이 부분은 pair를 사용하여도 된다) 모든 회의를 종료 시간이 빠른 순(만약 종료 시간이 같다면 시작 시간이 빠른 순)으로 정렬한 다음 모든 회의를 확인하면서 선택할 수 있는 가장 빨리 끝나는 회의를 선택하게 하였다.

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

struct meeting{
	int start,end;
};

int cmp(const meeting &a, const meeting &b){
	if(a.end == b.end)
		return a.start < b.start;
	return a.end < b.end;
}

int main() {
	int n,i,s,e,last=-1,c=0;
	meeting t;
	vector<meeting> v;
	scanf("%d",&n);
	for(i=0;i<n;i++){
		scanf("%d%d",&s,&e);
		t.start = s;
		t.end = e;
		v.push_back(t);
	}
	sort(v.begin(),v.end(),cmp);
	for(i=0;i<n;i++){
		if(v[i].start >= last){
			last = v[i].end;
			c++;
		}
	}
	printf("%d",c);
	return 0;
}

문제

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

풀이

주어진 N을 가지고 사면체를 최소로 만들어 N을 0으로 만드는것이 목표이다. 다르게 말하자면 그냥 동전 교환 문제이다.

만약 항상 한 개의 사면체를 만들만큼만 N이 주어진다면 좋겠지만 탐욕법으로 풀 수 있겠지만 동전 1문제 처럼 이 문제는 탐욕적으로 풀 수 없는 케이스가 있다.

예를들어 N이 50일때 탐욕법을 이용해 풀면 $45+3+1+1$가 답이되어 4개가 답이 되지만 실제로는 $20+20+10$로 3개가 최소이다.

동전 문제와는 다르게 이 문제는 사면체 수가 주어지지 않는데 이 값들은 여러번 사용할 것이므로 사면체 수를 구해놓고 배열에 저장해놓는다면 시간을 매우매우 줄일수 있다.

만약 입력값이 작다면 그냥 풀어도 되지만 문제 최대 입력이 300,000이고 이 값이 들어왔을때 메모이제이션을 적용하지 않는다면 시간 초과가 발생하게 된다. 메모이제이션은 이 문제에서 원하는 DP[N] = N으로 만들수 있는 최소 사면체 수로 적용하면 된다.

PS 처음에는 Top-down으로 풀려고 했는데 어쩌다보니 Bottom-up 풀이가 되어버렸다. 나중에 Top-down으로도 다시 짜봐야겠다.

//mincost[n] = n으로 만들수 있는 최소 사면체 수
//sum[n] = n 사이즈 사면체를 만드는데 필요한 대포알의 수

#include <stdio.h>
#define INT_MAX 98765431
int sum[130]={0},mincost[300001]={0};
int min(int a, int b){
	return a<b?a:b;
}
int solve(int ball, int pos,int count){
	if(ball<0) return INT_MAX;
	if(mincost[ball]) return mincost[ball];
	if(pos<1) return INT_MAX;
	if(ball == 0) return count;
	mincost[ball] = min(solve(ball-sum[pos],pos,count)+1, solve(ball,pos-1,count));
	return mincost[ball];
}
int main(){
	int i=0,n,maxp;
	scanf("%d",&n);
	while(++i){
		sum[i] = i*(i+1)*(i+2)/6;
		if(sum[i] >= 300000) break;
	}
	maxp=i-1;
	for(i=1;i<=n;i++){
		solve(i,maxp,0);
	}
	printf("%d",mincost[n]);
}