문제

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;
}