Mystika+Algorithm

BOJ 9358 - 순열 접기 게임

알고리즘/구현

문제

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


저작자 표시 비영리 변경 금지
신고

BOJ 2668 - 숫자고르기

알고리즘/DFS∕BFS

문제

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


저작자 표시 비영리 변경 금지
신고