백준15886 내 선물을 받아줘 2

작성일 | In

문제 링크

  • http://icpc.me/15886

문제 출처

  • 제2회 천하제일 코딩대회 예선 B번

풀이

sol 01

이 방법은 대회 도중 떠올린 방법입니다.
각각의 칸을 정점으로 잡고, 해당 칸에서 갈 수 있는 곳을 간선으로 잇는다면 그래프가 만들어집니다.
그래프를 모델링 한 후, in-degree가 가장 큰 노드부터 선물을 놓을 것입니다. 선물을 놓은 자리의 in-degree를 0으로 바꾸고 인접한 정점들의 in-degree도 0으로 바꿔주어 해당 자리에는 선물을 더이상 놓을 필요가 없다고 체크합니다.
위 작업을 모든 노드의 in-degree가 0이 될 때까지 반복해주면 정답을 얻을 수 있습니다.

sol 02

이 방법은 대회 공식 풀이입니다.
EW 구간 안에서는 밖으로 나갈 수 없고, 오직 밖에서 안쪽으로 들어올 수만 있습니다.
EW 구간마다 하나씩 선물을 놓으면 어느 위치에서든지 선물을 가져갈 수 있습니다.

전체 코드

sol 01

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#include <bits/stdc++.h>
using namespace std;

typedef pair<int, int> p;

char str[1001];
int cnt[1001] = {0};
vector<int> adj[1001];
int n;
int path[1001][1001];
int ans = 0;

void search(int n){
	path[n][n] = 1;
	int now = n;
	cnt[n]++;
	adj[n].push_back(n);
	if(str[n] == 'E') now++;
	else now--;
	while(path[n][now] == 0){
		path[n][now] = 1;
		adj[now].push_back(n);
		cnt[now]++;
		if(str[now] == 'E') now++;
		else now--;
	}
}

bool chk(){
	for(int i=0; i<n; i++) if(cnt[i] > 0) return false;
	return true;
}

int main(){
	scanf("%d", &n);
	scanf("%s", str);
	for(int i=0; i<n; i++) search(i);

	while(!chk()){
		int v = 0;
		for(int i=0; i<n; i++) if(cnt[v] < cnt[i] && cnt[i] > 0) v = i;
		cnt[v] = 0;
		for(int i=0; i<adj[v].size(); i++) cnt[adj[v][i]] = 0;
		ans++;
	}
	printf("%d", ans);
}

sol 02

1
2
3
4
5
6
7
8
9
10
11
#include <stdio.h>

int main(){
	int n; scanf("%d", &n);
	char str[1010]; scanf("%s", str);
	int ans = 0;
	for(int i=0; i<n-1; i++){
		if(str[i] == 'E' && str[i+1] == 'W') ans++;
	}
	printf("%d", ans);
}