블로그 이사 중입니다 >> gumgood.github.io

COCI 2009/2010 contest #2 풀이 본문

Problem Solving/주제별 풀이

COCI 2009/2010 contest #2 풀이

gumgood 2019. 9. 2. 15:35

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가 되기 위한 최소값을 구할 수 있다. 

#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가 몇 개식 포함하고 있는지를 모두 세어둔 후 가지고 있는 문자들로 만들 수 있는 수 중 가장 큰 값을 출력한다.

#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 역시 작도할 수 있다는 것이다.

#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[][]의 값이 더 작은 곳을 우선으로 탐색합니다.

#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한 횟수 + 위치가 다른 원소의 수'를 제시하는데 간단하게 반례를 만들 수가 있습니다. 결국 새로운 알고리즘을 알아내지 않는 한 아무도 못 푸는 문제입니다.

0 Comments
댓글쓰기 폼