[Csacademy] Csacademy Round #31 (Div. 2 only) 이야기

최근에 홈페이지 작업을 하느라 코딩 시험을 많이 못쳤다.

17/5/31일에 csa round#31이 열려 참가하게 되었는데 2시간 30분에 7문제를 푸는 라운드였다. 

오늘은 조금 아쉬운 날이기도 하다.

C번을 다풀어놓고 문제에서 분명히 말해둔 예외처리를 하지 않아서 틀리고 말았다.

레이팅은 그래도 +12점인 1389점으로 마무리했다.(50점 오를수있었는데 너무 아쉽다..)

(사실 피시방에서 친구들과 게임하면서 풀다가 C번이 1시간정도 안풀리길래 짜증나서 껐는데 답을 보니 예외처리를 하지 않았다..)

오랜만에 풀어본 문제인 만큼 또 문제를 설명해보고자 한다.

A. Insert In Sorted Array :: https://csacademy.com/contest/round-31/task/insert-in-sorted-array/

정렬된 배열속에 숫자 하나가 들어간다면 이 숫자는 몇번째 인덱스에 위치하게 될까? 라는 문제이다.

구현이고 간단하게 해결 할 수 있다.

시간복잡도는 O(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

#include <iostream> #include <cstdio> #include <vector>   using namespace std;   int arr[1002];   int main() {     int n, m;     scanf("%d %d",&n, &m);          for(int i = 0; i < n ; i ++)         scanf("%d",&arr[i]);          int cnt = 1;     for(int i = 0 ; i < n; i ++)         if(arr[i] <= m)             cnt++;          cout << cnt;     return 0; }   //                                                       This source code Copyright belongs to Crocus //                                                        If you want to see more? click here >>

Crocus

B. Karaoke Group :: https://csacademy.com/contest/round-31/task/karaoke-group/

친구들끼리 노래방을 갔는데 2명 이상 친구들이 그룹이 지어졌다고 가정했을 때 어느 그룹이 선호하는 노래가 가장 많이 중복되는지 찾아야 한다.

2명이상이라고 했지만 2명에 대해서 찾으면 된다. 왜냐하면 2명보다 많은 3명이 되면 그만큼 그룹이 커지기에 선호하는 노래의 교집합이 줄어들기 때문이다.

이 문제는 N제한을 자세히 보면 2<= N <= 100이다.

따라서 4중 포문을 이용하여 해결이 가능하다.

서로다른 두명의 친구를 고르고(i, j) 그 두 친구가 선호하는 노래 리스트 중(a,b) 교집합이 몇개가 되는지 찾고

두명의 친구를 모두 조사하고 난뒤 max를 구한다.

시간 복잡도는 O(n^4)이다.

#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
 
using namespace std;
 
vector<int> vc[102];
 
int main()
{
    int n, m;
    scanf("%d %d",&n, &m);
    
    for(int i = 1 ; i <= n ; i ++)
    {
        int k;
        scanf("%d",&k);
        
        for(int j = 0 ; j < k; j ++)
        {
            int val;
            scanf("%d", &val);
            vc[i].push_back(val);
        }
    }
    
    int cnt = 0;
    int ans = 0;
    for(int i = 1 ; i <= n - 1; i ++)
        for(int j = i + 1; j <= n; j ++)
        {
            int leni = vc[i].size();
            int lenj = vc[j].size();
            for(int a = 0 ; a < leni; a++)
                for(int b = 0 ; b < lenj ; b++)
                    if(vc[i][a] == vc[j][b])
                        cnt++;
            
            ans = max(ans, cnt);
            cnt = 0;
        }
    
    printf("%d",ans);
    return 0;
}
 
//                                                       This source code Copyright belongs to Crocus
//                                                        If you want to see more? click here >>

C. Recursive String :: https://csacademy.com/contest/round-31/task/recursive-string/

솔직히 이 문제는 풀면서 재미있었다.

규칙이 숨어있었고 그 규칙을 찾는 재미가 있었다.

string f(int N) {
  if (N == 0) return "a";
  if (N == 1) return "b";
  if (N == 2) return "c";
  return f(N - 1) + f(N - 2) + f(N - 3);
}

이 코드를 이용하여 문제를 풀어야 한다.

그런데 N이 35이고 K가 10억이다.

과연 재귀를 그것도 3개의 f를 재귀를 통해 알아봐야하는데 정말 이코드로 풀 수 있을까? 를 생각해봐야한다.

답은 절대 못푼다이다.

K가 10억이라함은 이미 10번째까지의 문자열이 없더라도 그만큼 큰 문자열이 생성될 수 있음을 암시하고 있는 것이고,

이렇게 쉬운 문제가 일단 C번에 있을 수 없다는 것 또한 마찬가지이다.

그래서 이런 문제가 나오면 필자는 종종 규칙을 알아보곤 한다.

규칙은 눈으로 안보이다. 직접 적어봐야 안다.

필자는 이 문제를 풀기위해 규칙을 찾기위해 우선 위의 코드로 대충 이 코드가 어떻게 돌아가는지 보았다.

1일때 1

c

2일때 1

c

3일때 3

cba

4일때 5

cbacb

5일때 9

cbacbcbac

6일때 17

cbacbcbaccbacbcba

7일때 31

cbacbcbaccbacbcbacbacbcbaccbacb

8일때 57

cbacbcbaccbacbcbacbacbcbaccbacbcbacbcbaccbacbcbacbacbcbac

...

이때 눈치를 챘다.

수가 증가하는 점화식이 A[i] = A[i-1] + A[i-2] + A[i-3]으로 증가한다.

즉 8일때는 5 6 7일때의 값을 더하면 된다.

하지만 이걸로는 k번째 문자가 무엇인지는 알 수 없다.

이때문에 30분 넘게 고민한 결과 조금 더 원시적으로 들어가보기로 했다.

그 결과 

4 = 2 1 0 2 1

5 = 2 1 0 2 1 2 1 0 2

6 = 2 1 0 2 1 2 1 0 2 / 2 1 0 2 1 / 2 1 0 

7 = 2 1 0 2 1 2 1 0 2 2 1 0 2 1 2 1 0 / 2 1 0 2 1 2 1 0 2 / 2 1 0 2 1

라는 결과를 보았는데 이는,

4일때는 3 2 1인데 3은 2 1 0이기에 4는 2 1 0 2 1이다.

이런것처럼 7은 6 5 4인데 6과 5와 4가 각각 위와 같기에

7은 저렇게 나타낼 수 있다.

그럼 다시 생각해보자. k번째는 결국 6 5 4에서의 x번째와 같아질 수 있게 된다.

만약 7의 값 속에서 6의 값 내에 k번째가 있었다면

6 = 2 1 0 2 1 2 1 0 2 2 1 0 2 1 2 1 0 이 값 내에서 k번째를 찾아도 된다.

7의 값 속에서 5의 값 내에 k번째가 있었다면

'7일때 길이 - 6일때 길이'에서 'k - 6일때 길이' 번째를 구하면 된다.

그렇게 계속 내려오며 n이 0,1,2,3 중 하나의 값이 될 때 까지 반복한다.(그렇게되면 우리는 바로 O(1)만에 k번째 값을 찾을 수 있다.)

(코드로 보면 더 쉽다.)

여기까진 모두 구했는데 k가 n번째 길이보다 더 크게 나와있을 때 -1을 넣으라 했는데 그 과정을 빠트리고 틀려버려서 이문제가 너무 아쉬웠다.

전체 시간 복잡도는 O(n)에 해결된다.

#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <string>
 
using namespace std;
 
long long arr[40];
 
int main()
{
    int n, k;
    scanf("%d %d",&n, &k);
    
    arr[0] = 1;
    arr[1] = 1;
    arr[2] = 1;
    arr[3] = 3;
    arr[4] = 5;
    
    for(int i = 5; i <= 35; i++)
        arr[i] = arr[i-1] + arr[i-2] + arr[i-3];
        
    if(arr[n] < k)
    {
        printf("-1");
        return 0;
    }
    
    while(!(0 <= n && n <= 3))
    {
        if(k <= arr[n - 1])
            n--;
        else if(arr[n-1] < k && k <= arr[n-1] + arr[n-2])
        {
            k -= arr[n-1];
            n-=2;        
        }
        else if(arr[n-1] + arr[n-2] < k && k <= arr[n-1] + arr[n-2] + arr[n-3])
        {
            k -= (arr[n-1] + arr[n-2]);
            n-=3;
        }
        else
            break;
    }
    
    if(n == 3)
    {
        if(k == 1)
            cout << "c";
        else if(k == 2)
            cout << "b";
        else
            cout << "a";
    }
    else if(n == 2)
        cout << "c";
    else if(n == 1)
        cout << "b";
    else
        cout << "a";
 
    return 0;
}
 
//                                                       This source code Copyright belongs to Crocus
//                                                        If you want to see more? click here >>