문제

https://algospot.com/judge/problem/read/SNAIL

풀이

완전 탐색 코드를 먼저 만들었다. 비가 올 확률이 75%이고 비가 올때는 2m, 비가 오지 않을 확률이 25%이고 비가 오지 않을때는 1m씩 올라가므로 그냥 재귀적으로 함수를 호출해주며 m일이 지났을때 우물을 다 올라갔는지 확인해주는 코드를 작성했다.

#include <cstdio>
int n,m;
double solve(int cur, int day){
	if(day == m) return cur >= n;
	return (0.25*solve(cur+1,day+1)) + (0.75*solve(cur+2,day+1));
}
int main() {
	int t;
	scanf("%d",&t);
	while(t--){
		scanf("%d%d",&n,&m);
		printf("%.10lf\n",solve(0,0));
	}
}

잘 작동하지만 완전 탐색인만큼 큰 입력이 들어오면 엄청 오래 걸린다. 그러므로 메모이제이션을 적용해서 중복 계산을 하지 않도록 코드를 바꿔줘야 한다. dp[height][day] = day일째에 height만큼 올라 왔을때 우물 끝까지 올라갈 확률이라 하고 메모이제이션을 적용했다.

또한 아래와 같은 부분에 대해 고민을 하며 코드를 작성했다.

• double은 -1로 memset이 안되는거 같다. > 그래서 직접 for문으로 값을 초기화시켰다.
• 올라갈 수 있는 최대 높이는 N이 아니다. > N-1에서 비가 와 N+1까지 올라갈 수 있는 경우가 있으므로 배열 크기를 1 더 잡아줘야 한다.

#include <cstdio>
int n,m;
double dp[1003][1001];
double solve(int cur, int day){
	if(day == m) return cur >= n;
	if(cur >= n) return 1.;
	double& ret = dp[cur][day];
	if(ret != -1.)	return ret;
	return ret = (0.25*solve(cur+1,day+1)) + (0.75*solve(cur+2,day+1));
}
int main() {
	int t;
	scanf("%d",&t);
	while(t--){
		scanf("%d%d",&n,&m);
		for(int i=0;i<=1002;i++)
			for(int j=0;j<=1000;j++)
				dp[i][j] = -1.0;
		printf("%.10lf\n",solve(0,0));
	}
}

문제

https://algospot.com/judge/problem/read/ZEROONE

풀이

그냥 문제대로 구현하면 푸는 문제인줄 알고 풀었다가 엄청 많이 틀렸다. 문자열의 최대 길이가 L이라했을때 별 다른 방법 없이 코드를 작성하면 전체 수행시간이 $O(NL)$이라 시간 초과가 나게 된다. 그러므로 수행 시간의 상한을 $O(N * lg(L))$ 정도라 생각하고 풀어야 한다.

수열의 값은 0과 1밖에 없고 최대값과 최소값이 같다는 뜻은 해당 구간 i,j의 모든 원소가 같다는 뜻이므로 구간마다 그룹을 나누어 배열에 저장하면 전체 수행 시간을 $O(N)$으로 줄일 수 있다.

예를들어 수열 000110010가 있다 할때 그룹화하여 000112234로 저장한뒤 그룹 배열의 i와 j번째 값이 같은지만 비교해주면 되기 때문이다.

#include <stdio.h>
int main() {
	int t,i,j,tmp;
	int diff[1000001]={0};
	char s[1000001];
	scanf("%s",s);
	for(i=1;s[i]!='\0';i++){
		diff[i] = diff[i-1];
		if(s[i-1] != s[i]) diff[i]++;
	}
	scanf("%d",&t);
	while(t--){
		scanf("%d%d",&i,&j);
		printf("%s\n",diff[i] == diff[j]?"Yes":"No");
	}
	return 0;
}

문제

https://algospot.com/judge/problem/read/JLIS

풀이

이 문제를 완전 처음에.. 그러니까 동적계획법이 뭔지도 모르고 접했을때는 그냥 두 수열을 중복되는 수 없이 한 수열로 합친 다음에 합친 수열의 길이를 출력하게 했다. 놀랍게도 이 방식이 예제 입력에 대해서는 제대로 된 답을 출력해주기 때문에 코드를 제출했으나 당연히 WA를 받았다.

그리고 몇 일 전에 LIS 문제를 해결한 뒤 이 문제를 다시 접했는데 이 때는 LIS와 비슷하게 해결하면 될 줄 알았다. 두 수열의 LIS를 각각 구한뒤 각 수열의 길이를 출력하는 방법을 생각해보았으나 세 번째 예제인 $A=\{10, 20, 30\}, B=\{10, 20, 30, 1, 2\}$같은 경우에서는 A,B 수열 모두 $\{10, 20, 30\}$가 LIS이므로 6을 반환하지만 실제로는 $A=\{10, 20, 30\}, B=\{1, 2\}$인 5가 답이다.

LIS 문제는 한 개의 수열에 대한 인덱스 값을 인수로 받는 solve(int)를 작성했었는데 이 문제도 비슷하게 두개의 수열의 인덱스 값을 각각 받는 solve(int, int)를 작성하면 될 것 같았다. 문제를 해결하는 코드를 작성하면서 아래와 같은 부분에 대해 유의하며 작성했다.

• 모든 원소의 값은 signed integer 범위에 들어간다. 즉, 최소값은 INT_MIN이다.
• 한 수열의 원소를 아무것도 선택하지 않는 상태가 있을 수 있다.

#include <cstdio>
#include <cstring>
#include <climits>
int n,m,A[100],B[100],dp[101][101];
int max(int a, int b){return a>b?a:b;}
int solve(int Ai, int Bi){
	int &ret = dp[Ai+1][Bi+1];
	if(ret != -1) return ret;
	ret = 0;
	int pA, pB, pivot;
	pA = Ai == -1 ? INT_MIN : A[Ai];
	pB = Bi == -1 ? INT_MIN : B[Bi];
	pivot = max(pA,pB);
	for(int i=Ai+1;i<n;i++)
		if(pivot < A[i])
			ret = max(ret, solve(i,Bi)+1);
	for(int i=Bi+1;i<m;i++)
		if(pivot < B[i])
			ret = max(ret, solve(Ai,i)+1);
	return ret;
}
int main() {
	int t;
	scanf("%d",&t);
	while(t--){
		int i;
		memset(A,0,sizeof(A));
		memset(B,0,sizeof(B));
		memset(dp,-1,sizeof(int)*101*101);
		scanf("%d%d",&n,&m);
		for(i=0;i<n;i++)
			scanf("%d",&A[i]);
		for(i=0;i<m;i++)
			scanf("%d",&B[i]); 
		printf("%d\n",solve(-1,-1));
	}
}

문제

#include <stdio.h>
int n,num[500];
int max(int a,int b){return a>b?a:b;}
int solve(int pos){
	int i, ret = 0;
	for(i=pos+1;i<n;i++){
		if(num[pos] < num[i]){
			ret = max(ret, solve(i)+1);
		}
	}
	return ret;
}
int main(void) {
	int i,t;
	scanf("%d",&t);
	while(t--){
		int ans = 0;
		scanf("%d",&n);
		for(i=0;i<n;i++){
			scanf("%d",&num[i]);
		}
		for(i=0;i<n-1;i++){
			ans = max(ans, solve(i));
		}
		printf("%d\n",ans);
	}
	return 0;
}

위 코드는 메모이제이션을 적용하지 않은 코드라 같은 값을 여러번 구한다. 그러니 여기서 메모이제이션을 적용해줘야한다. 메모이제이션을 적용할 dp 배열을 만들고 dp[x] = x번째 수부터 시작할때 가장 긴 LIS의 길이의 값을 저장하게 하였다.

#include <stdio.h>
#include <string.h>
int n,num[500],dp[500]; //dp[x] == -1이면 x번째 수부터 시작하는 LIS 길이를 아직 구하지 않은것이다
int max(int a,int b){return a>b?a:b;}
int solve(int pos){
	int i, ret = 1;
	//이미 pos번째 수부터 시작하는 LIS 길이를 구했다면 바로 반환한다.
	if(dp[pos] != -1) return dp[pos];
	
	//pos번째 수보다 뒤에있는 더 큰 모든 수들을 확인하며 LIS의 길이를 찾는다.
	for(i=pos+1;i<n;i++)
		if(num[pos] < num[i])
			ret = max(ret, solve(i)+1);
	//메모이제이션하고 반환한다.
	return dp[pos] = ret;
}
int main(void) {
	int i,t;
	scanf("%d",&t);
	while(t--){
		int ans = 0;
		memset(dp,-1,sizeof(dp));
		scanf("%d",&n);
		for(i=0;i<n;i++)
			scanf("%d",&num[i]);
		//0번째 수부터 n-1번째 수까지 돌면서 LIS 길이를 찾는다.
		for(i=0;i<n-1;i++)
			ans = max(ans, solve(i));
		
		printf("%d\n",ans);
	}
	return 0;
}

문제

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

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

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

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

코드는 아래와 같이 짰다. 회의의 시작시간과 종료 시간을 가지고 있는 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;
}