COCI 2009/2010 contest #2 개인 풀이
COCI(Croatian Open Competition in Informatics) 2009/2010 contest #2
https://www.acmicpc.net/category/detail/84
1. BOJ 2914 저작권
앨범의 수록곡의 개수 A와 수록곡 당 멜로디의 개수의 평균값 I가 주어질 때, 적어도 몇 개의 멜로디가 있는지 묻는다. 이 문제에서는 평균값을 구할 때 올림을 사용하므로 실제 평균 avg는 I-1 < avg <= I을 만족해야 한다. 상한이 폐구간이므로 어떤 평균값 I가 되기 위한 avg의 상한을 구할 수 있다. 따라서 I-1이 되기 위한 avg의 상한을 구하고 그 값보다 멜로디가 1만큼 더 있으면 올림한 평균값 I가 되기 위한 최소값을 구할 수 있다.
1
2
3
4
5
6
7
#include<stdio.h>
int main()
{
int a,b;
scanf("%d%d",&a,&b);
printf("%d",a*(b-1)+1);
}
2. BOJ 2915 로마 숫자 재배치
Brute Force로 해결할 수 있다. 입력에 문자 I, V, X, L, C가 몇 개식 나오는지 세어둔다. 1 ~ 100 사이의 수에 대해 각 수가 문자 I, V, X, L, C를 몇 개식 포함하고 있는지 모두 세어둔 후 가지고 있는 문자들로 만들 수 있는 수 중 가장 큰 값을 출력한다.
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
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
#include<cstdio>
int i, v, x, l, c;
int I[101], V[101], X[101], L[101], C[101];
void solve(){
for (int i=0; i<10; ++i){
I[i*10 + 1] += 1, I[i*10 + 6] += 1;
I[i*10 + 2] += 2, I[i*10 + 7] += 2;
I[i*10 + 3] += 3, I[i*10 + 8] += 3;
I[i*10 + 4] += 1, I[i*10 + 9] += 1;
V[i*10 + 4]++;
V[i*10 + 5]++;
V[i*10 + 6]++;
V[i*10 + 7]++;
V[i*10 + 8]++;
X[i*10 + 9]++;
}
for (int i=0; i<10; ++i){
X[10 + i] += 1, X[60 + i] += 1;
X[20 + i] += 2, X[70 + i] += 2;
X[30 + i] += 3, X[80 + i] += 3;
X[40 + i] += 1, X[90 + i] += 1;
L[40 + i]++;
L[50 + i]++;
L[60 + i]++;
L[70 + i]++;
L[80 + i]++;
C[90 + i]++;
}
int n;
for (int m=100; m; --m)
if (i==I[m] && v==V[m] && x == X[m] && l == L[m] && c == C[m])
n = m;
if (n/10==1) printf("%s", "X");
if (n/10==2) printf("%s", "XX");
if (n/10==3) printf("%s", "XXX");
if (n/10==4) printf("%s", "XL");
if (n/10==5) printf("%s", "L");
if (n/10==6) printf("%s", "LX");
if (n/10==7) printf("%s", "LXX");
if (n/10==8) printf("%s", "LXXX");
if (n/10==9) printf("%s", "XC");
if (n%10==1) printf("%s", "I");
if (n%10==2) printf("%s", "II");
if (n%10==3) printf("%s", "III");
if (n%10==4) printf("%s", "IV");
if (n%10==5) printf("%s", "V");
if (n%10==6) printf("%s", "VI");
if (n%10==7) printf("%s", "VII");
if (n%10==8) printf("%s", "VIII");
if (n%10==9) printf("%s", "IX");
}
int main(){
char in[10]; scanf("%s", in);
for (int j=0; in[j]; ++j){
if (in[j]=='I') i++;
if (in[j]=='V') v++;
if (in[j]=='X') x++;
if (in[j]=='L') l++;
if (in[j]=='C') c++;
}
solve();
}
3. BOJ 2916 자와 각도기
만들 수 있는 degree를 check한 배열을 deg[]라 하자. 각이 주어지지 않을 경우 0도만 작도할 수 있다.
degree 하나가 추가될 경우 기존에 만들 수 있는 degree들에 더하거나 빼는 것으로 새로운 각도를 작도할 수 있다. 유의할 점은 각도 n을 작도할 수 있을 때, 360-n 역시 작도할 수 있다는 것이다.
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
#include<bits/stdc++.h>
using namespace std;
bool deg[360];
void push(int d){
vector<int> newdeg;
deg[d] = true;
for(int i=0;i<360;++i)
if(deg[i]){
int n = (i+d)%360;
if(!deg[n])
newdeg.push_back(n);
if(!deg[360-n])
newdeg.push_back(360-n);
n = (i-d+360)%360;
if(!deg[n])
newdeg.push_back(n);
if(!deg[360-n])
newdeg.push_back(360-n);
}
for(int i : newdeg)
push(i);
}
int main(){
int n, k, d;
scanf("%d%d",&n,&k);
deg[0] = true;
for(int i=0;i<n;++i){
scanf("%d",&d);
push(d);
}
for(int i=0;i<k;++i){
scanf("%d",&d);
if(deg[d])
puts("YES");
else
puts("NO");
}
}
4. BOJ 2917 늑대 사냥꾼
두 번의 그래프 탐색으로 해결할 수 있다. 첫 번째 그래프 탐색은 각 지점과 나무 사이의 거리를 기록한 배열 d[][]를 만듭니다. 각 나무들이 거리가 0인 bfs의 시작점으로 생각할 수 있습니다. 두 번째 그래프 탐색은 오두막으로 이동하되 지나치는 d[][]의 값이 더 작은 곳을 우선으로 탐색합니다.
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
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
#include<bits/stdc++.h>
using namespace std;
const int dx[] = {-1,1,0,0};
const int dy[] = {0,0,-1,1};
int n, m;
char in[500][501];
int sx, sy, ex, ey;
int dist[500][500];
void build(){
queue<tuple<int,int,int>> q;
memset(dist,-1,sizeof(dist));
for(int i=0;i<n;++i)
for(int j=0;j<m;++j){
if(in[i][j]=='V')
sx = i, sy = j;
if(in[i][j]=='J')
ex = i, ey = j;
if(in[i][j]=='+'){
dist[i][j] = 0;
q.push({i,j,0});
}
}
while(!q.empty()){
int x, y, d;
tie(x,y,d) = q.front(); q.pop();
for(int i=0;i<4;++i){
int nx = x + dx[i];
int ny = y + dy[i];
if(nx<0 || n<=nx) continue;
if(ny<0 || m<=ny) continue;
if(dist[nx][ny] != -1) continue;
dist[nx][ny] = d+1;
q.push({nx,ny,d+1});
}
}
}
int solve(){
build();
int ans = 0;
priority_queue<tuple<int,int,int>> pq;
bool v[500][500] = {0};
ans = dist[sx][sy];
pq.push({dist[sx][sy],sx,sy});
v[sx][sy] = true;
while(!pq.empty()){
int x, y, d;
tie(d,x,y) = pq.top(); pq.pop();
ans = min(ans, d);
if(x==ex && y==ey) return ans;
for(int i=0;i<4;++i){
int nx = x + dx[i];
int ny = y + dy[i];
if(nx<0 || n<=nx) continue;
if(ny<0 || m<=ny) continue;
if(v[nx][ny]) continue;
v[nx][ny] = true;
pq.push({dist[nx][ny],nx,ny});
}
}
return 0;
}
int main(){
scanf("%d%d\n",&n,&m);
for(int i=0;i<n;++i)
scanf("%s",in[i]);
printf("%d",solve());
}
5. BOJ 2918 Arrange
공식 풀이에 반례가 있는 문제입니다(…). 풀이에서는 Bidirectional Search와 A* search algorithm을 해답으로 제시하고 있습니다. 전자의 경우 시간복잡도는 $O(b^{d/2})$로 b는 최대 66이며 이 때 d = 5만 되어도 시간초과가 납니다. A* search algorithm의 경우 휴리스틱 함수로 ‘swap한 횟수 + 위치가 다른 원소의 수’를 제시하는데 간단하게 반례를 만들 수가 있습니다. 결국 새로운 알고리즘을 알아내지 않는 한 아무도 못 푸는 문제입니다.