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

COCI 2009/2010 contest #1 풀이 본문

Problem Solving/주제별 풀이

COCI 2009/2010 contest #1 풀이

gumgood 2019. 8. 2. 15:11

COCI(Croatian Open Competition in Informatics) 2009/2010 contest #1

https://www.acmicpc.net/category/detail/83

 

1. BOJ 2920 음계

음계가 "1 2 3 4 5 6 7 8"이면 ascending, "8 7 6 5 4 3 2 1"이면 descending을 출력하고, 나머지는 mixed를 출력한다.

stl vector의 비교연산자로 간결하게 구현한다.

#include<bits/stdc++.h>
using namespace std;

vector<int> as = {1,2,3,4,5,6,7,8};
vector<int> ds = {8,7,6,5,4,3,2,1};
vector<int> in(8);

int main(){
  for(int i=0;i<8;++i)
    scanf("%d",&in[i]);
  if(in==as)
    printf("ascending");
  else if(in==ds)
    printf("descending");
  else
    printf("mixed");
}

 

2. BOJ 2921 도미노

도미노 위의 숫자는 up, 밑의 숫자는 down에 저장하고 brute force. 

#include<cstdio>

int main(){
    int n;
    scanf("%d",&n);

    int ans = 0;
    for(int up=0;up<=n;++up)
        for(int down=up;down<=n;++down)
            ans += up+down;
    printf("%d",ans);
    return 0;
}

 

3. BOJ 2922 즐거운 단어

핵심은 '단어에 포함된 밑 줄의 개수는 최대 10개'이다. 한 알파벳은 L, L이 아닌 자음, 모음 세가지로 분류할 수 있다. 밑 줄이 있는 칸에 알파벳이 들어가는 경우는 3가지이므로 전체 경우의 수가 3^10 = 59049가지이다. 각 단어에 대해 즐거운 단어인지 확인할 때 O(n)가 걸리는데 n이 충분히 작기 때문에 brute force로 해결할 수 있다.

#include<bits/stdc++.h>
using namespace std;

bool vowel(char c){
  if(c=='A'||c=='E'||c=='I'||c=='O'||c=='U')
    return true;
  return false;
}

char s[101];

long long solve(int idx,bool L){
  long long ret = 0;
  for(int i=idx;s[i];++i){
    if(s[i]=='_'){
      s[i] = 'A';
      ret += 5LL*solve(i,L);
      s[i] = 'B';
      ret += 20LL*solve(i,L);
      s[i] = 'L';
      ret += solve(i,true);
      s[i] = '_';
      return ret;
    }else{
      if(s[i]=='L') L = true;
      if(i-2>=0){
        if(vowel(s[i]) && vowel(s[i-1]) && vowel(s[i-2]))
          return 0LL;
        if(!vowel(s[i]) && !vowel(s[i-1]) && !vowel(s[i-2]))
          return 0LL;
      }
    }
  }
  return L;
}

int main(){
  scanf("%s",s);
  printf("%lld",solve(0,false));
}

 

4. BOJ 2923 숫자 게임

모든 (\(a_i\), \(b_i\))쌍들 중 \(\max_{i \in n} (a_i+b_i)\)가 가장 작으려면 \(a_i\)는 오름차순으로 \(b_i\)은 내림차순으로 쌍을 지어주면 된다. (간단하게 증명할 수 있다). 문제는 매번 숫자를 추가하고 '모든 쌍의 합의 최댓값의 최솟값'을 찾아야 한다. 

 

N은 100000이지만 각 숫자의 범위가 [1, 100]이므로 우선 \(a_i\)와 \(b_i\)를 버킷정렬한 뒤 각 버킷을 유지한다. 버킷을 유지하는 이유는 숫자를 추가시키는데 O(1)이 걸리고, 10만개의 숫자를 1~100의 index로 압축해서 다룰 수 있기 때문이다. A의 버킷들을 오름차순으로, B의 버킷들을 내림차순으로 이동하면서 모든 (\(a_i\), \(b_i\))쌍을 확인할 수 있다. 버킷은 최대 100개이기 때문에 각 라운드에 대해 숫자를 추가하고 값을 찾는데 O(100)=O(1)가 걸린다. 전체 시간복잡도 \(O(n)\)에 해결 가능하다.

#include<bits/stdc++.h>
using namespace std;

int N;
vector<int> A(101), B(101);

int solve(){
  int ret = 0;
  vector<int> X=A, Y=B;
  for(int i=1, j=100; i<=100 && j>=1;){
    if(X[i] < Y[j]){
      if(X[i]){
        ret = max(ret, i+j);
        Y[j] -= X[i];
      }
      i++;
    }else{
      if(Y[j]){
        ret = max(ret, i+j);
        X[i] -= Y[j];
      }
      j--;
    }
  }
  return ret;
}

int main(){
  scanf("%d",&N);
  while(N--){
    int a, b;
    scanf("%d%d",&a,&b);
    A[a]++, B[b]++;
    printf("%d\n",solve());
  }
}

 

5. BOJ 2924 천재

successor graph가 주어질 때, 각 노드가 한 번에 한 edge만큼 이동한다. A번째 ~ B번째까지의 상태에 대해서 C개 ~ N-D개의 노드가 처음 상태의 노드와 완전히 일치하는 상태가 몇개인지 출력한다.

 

우선 dfs를 돌면서 각 노드가 가지는 사이클의 길이(하나의 노드는 크기가 1인 사이클)를 저장한다. C ~ N-D번째 노드들에 대해 사이클 크기의 최소공배수를 찾으면, 몇 번마다 첫 상태와 일치해지는 지 알 수 있다. 이로부터 A~B번째에 몇 번 일치하는지 역시 알 수 있다.

#include<bits/stdc++.h>
using namespace std;

int gcd(int a,int b){
  return b ? gcd(b, a%b) : a;
}
int lcm(int a,int b){
  return a/gcd(a,b)*b;
}

int N, A, B, C, D;
int s[500001];

int cnt[500001];

int solve(){
  for(int i=1;i<=N;++i)
    if(cnt[i]==0){
      stack<int> st;
      st.push(i);
      for(int j=s[i]; j!=i; j=s[j])
        st.push(j);
      int size = st.size();
      for(; !st.empty(); st.pop())
        cnt[st.top()] = size;
    }

  int T = 1;
  for(int i=1+C;i<=N-D;++i)
    T = lcm(T, cnt[i]);
  return (B+T-1)/T - ((A-1)+T-1)/T;
}

int main(){
  scanf("%d%d%d%d%d",&N,&A,&B,&C,&D);
  for(int i=1;i<=N;++i)
    scanf("%d",s+i);

  int ans = solve();
  printf("%d",ans);
}

 

6. BOJ 2925 신기한 물체

모르겠다

Tag
, ,
0 Comments
댓글쓰기 폼