문제

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

풀이

주어진 수열의 첫번째 수와 N번째 수를 더해 새 수열에 넣고, 두번째 수와 N-1번째 수를 더해 다시 새 수열에 넣고.. 이 작업을 수열의 길이가 2가 될 때까지 반복한 후 왼쪽 수가 큰지 오른쪽 수가 큰지 비교하는 문제이다.

이 문제는 양방향 큐, 즉 Deque(Double Ended Queue, [덱])를 사용하면 쉽게 풀수 있다. 새 수열을 만드는 과정에서 왼쪽 수(front)와 오른쪽 수(back)를 쉽게 큐에서 꺼낼수(pop) 있어 전체적인 코드가 짧아지고 구현이 간편해진다.

#include <cstdio>
#include <deque>
using namespace std;

int main() {
	int t,i,j,x,n;
	scanf("%d",&t);
	for(i=1;i<=t;i++){
		scanf("%d",&n);
		deque<int> dq;
		for(j=0;j<n;j++){
			scanf("%d",&x);
			dq.push_back(x);
		}
		while(1){
			if(dq.size() == 2) break;
			deque<int> cur;
			while(!dq.empty()){
				cur.push_back(dq.front()+dq.back());
				dq.pop_front();
				if(!dq.empty()) dq.pop_back();
			}
			while(!cur.empty()){
				dq.push_back(cur.front());
				cur.pop_front();
			}
		}
		printf("Case #%d: %s\n",i,dq[0]>dq[1]?"Alice":"Bob");
	}
	return 0;
}

문제

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

풀이

주어진 배열에서 순환하는 요소가 총 몇개인지 카운팅하고, 순환하는 요소들을 오름차순으로 출력하는 문제이다. 아래의 예제 이미지를 보면 순환하는 요소는 1-3, 5 이렇게 3개이다.

정점 N에서 시작하는 순환 배열이 존재하는가를 확인하려면 도착점을 N으로 두고 MAP[N]부터 시작해서 마지막에 N으로 오는가를 확인하면 된다. 만약 N으로 오지 않고 이미 방문했던 정점을 다시 방문한다면 순환 배열이 존재하지 않는다는 뜻이다.

나는 따로 방문을 표시할 배열과 사이클 여부를 표시할 배열을 따로 만들지 않고 방문을 표시할 배열의 값을 0, 1, 2로 구분지어 방문하지 않음, 방문함, 이미 방문했고 사이클이다 라고 정의하여 O(2N)의 공간을 사용하였다.

#include <stdio.h>
int n,map[101]={0},visit[101]={0};
int isCircular(int start, int cur, int count){
	if(visit[cur]) return 0;
	visit[cur] = 1;
	if(start == cur) {
		
		int i;
		for(i=1;i<=n;i++){
			if(visit[i] == 1) visit[i]=2;
		}
		return count+1;
	}
	return isCircular(start,map[cur],count+1);
}
int main(){
	int i,j,ans=0;
	scanf("%d",&n);
	for(i=1;i<=n;i++) scanf("%d",&map[i]);
	for(i=1;i<=n;i++){
		for(j=1;j<=n;j++){
			if(visit[j]==1) visit[j]=0;
		}
		ans += isCircular(i,map[i],0);
	}
	printf("%d\n",ans);
	for(i=1;i<=n;i++){
		if(visit[i]==2)
			printf("%d\n", i);
	}
}

문제

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

풀이

수빈이가 좌표 N에서 동생이 있는 좌표 K를 찾아가야하는데 수빈이가 동생을 찾는 가장 빠른 시간, 즉 최소 비용을 찾는 문제다. 수빈이는 걷거나 순간 이동을 할 수 있는데 수빈이의 현재 좌표를 X라 할때 X+1, X-1, X*2로 이동할 수 있으며 모든 동작에는 1초의 시간이 걸린다고 한다. 최소 비용을 찾고, 모든 정점의 가중치가 1(초)로 똑같기 때문에 BFS로 해결 할 수 있다. 풀면서 아래의 조건을 체크하여 반복 횟수를 줄였다.

1. (당연하지만) 한번 방문한 정점은 다시 안가도 된다. 
2. 최소 비용이 될 수 있는 후보 중 가장 작은 값보다 현재 비용이 크다면 바로 답이 아니라 간주한다.

#include <cstdio>
#include <queue>
using namespace std;
struct movement{
	int x,step;
};
queue<movement> q;
int visit[100001] = {0};
int abs(int x) {return x>0?x:-x;}
int main(){
	int n,k,i,ans;
	movement move;
	
	scanf("%d%d",&n,&k);
	move.x = n;
	move.step = 0;
	
	ans=abs(n-k);

	if(n >= k){
		printf("%d",ans);
		return 0;
	}

	q.push(move);
	while(!q.empty()){
		q.front();
		
		if(q.front().step >= ans){
			q.pop();
			continue;
		}

		if(q.front().x == k) {
			ans = q.front().step;
			q.pop();
			continue;
		}

		move.step = q.front().step + 1;

		if(q.front().x*2 <= 100000 && q.front().x*2 >= 0 && !visit[q.front().x*2]){
			move.x = q.front().x * 2;
			visit[move.x] = 1;
			q.push(move);
		}

		if(q.front().x +1 <= 100000 && !visit[q.front().x+1]) {
			move.x = q.front().x + 1;
			visit[move.x] = 1;
			q.push(move);
		}
		if(q.front().x - 1 >= 0 && !visit[q.front().x-1]){
			move.x = q.front().x - 1;	
			visit[move.x] = 1;
			q.push(move);
		}
		q.pop();
	}
	printf("%d",ans);
}

문제

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

풀이

1과 00만을 이용한 길이가 N인 이진 수열이 몇개인지 찾는 문제이다. 1과 00만을 사용해야 해야하므로 0이 혼자 쓰여서는 안된다. 이 문제는 직접 몇 개의 케이스를 손으로 적어서 풀었다.

DP[1] = 1

DP[2] = 11, 00

DP[3] = 111, 100, 001

DP[4] = 1111, 1100, 1001, 0011, 0000

DP[5] = 11111, 11001, 10011, 10000, 00001, 00100, 00111, 01001

...

길이가 N일때의 갯수를 세어보면 $ DP[N] = DP[N-1] + DP[N-2] $, 즉 이 문제는 단순한 N번째 피보나치 수를 구하는 문제와 같다.

#include <stdio.h>
int dp[1000001];
int solve(int x){
	if(dp[x]) return dp[x];
	return dp[x] = (solve(x-1) + solve(x-2)) % 15746;
}
int main() {
	int n;
	dp[1] = 1;
	dp[2] = 2;
	dp[3] = 3;
	scanf("%d",&n);
	printf("%d",solve(n));
}

문제

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

풀이

나는 가장 먼저 이 문제는 정해진 범위의 소수만을 다루면서 여러 테이스 케이스를 입력받기 때문에 미리 소수를 판별하는 테이블을 만들어 놓았다. 그리고 현재 비밀번호와 현재 비밀번호까지 오는데 몇 번이나 거쳤는지 저장하기 위해 change라는 구조체를 만들어 <queue>에 넣고 1000의 자리부터 1의 자리까지 모두 0~9를 대입하며 큐에 넣고 방문했다는 표시를하여 다시 그 수로 돌아오지 못하게 하여 최소 경로를 찾게 하였다.

#include <cstdio>
#include <cmath>
#include <queue>
using namespace std;
struct change{
	int pw,step;
};
int prime[10000]={0};
int main(){
	int t,i,j;
	double sq;
	scanf("%d",&t);
	for(i=1000;i<=9999;i++){
		sq = sqrt((double)i);
		for(j=2;j<=sq;j++){
			if(i%j==0){
				prime[i] = 1;
				break;
			}
		}
	}
	while(t--){
		int visit[10000] = {0};
		queue<change> q;
		change chg;
		int from,dest,digit,rest,ans=987654321;
		scanf("%d%d",&from,&dest);
		chg.pw = from;
		chg.step = 0;
		visit[from] = 1;
		q.push(chg);
		while(!q.empty()){
			if(q.front().step >= ans){
				q.pop();
				continue;
			}
			if(q.front().pw == dest){
				ans = q.front().step;
				q.pop();
				continue;
			}
			for(i=1;i<=1000;i*=10){
				rest = q.front().pw - ((q.front().pw / i) % 10) * i;
				for(j=0;j<=9;j++){
					if(i==1000&&!j) continue;
					if(prime[j*i+rest]||visit[j*i+rest]) continue;
					chg.pw = j*i+rest;
					chg.step = q.front().step + 1;
					q.push(chg);
					visit[chg.pw] = 1;
				}
			}
			q.pop();
		}
		printf("%d\n",ans);
	}
}