[Csacademy] Csacademy Round #24 이야기

확실히 예전에 비해 문제를 볼때 조금 편해진 것 같다.

예전에는 코포이건 cs이건 처음에는 긴장되었었는데, 이제는 편안하게 문제를 풀 수 있게 된 것 같다.

한가지 고쳐지지 않는건 C번만 가면 풀지 못하는 것.

Rating을 1363(-17)로 마무리하였다.

잘할 수 있을 것 같은 시험이었는데 잘 못했다.

A, B번을 30분동안 다 풀어서 이제 C번을 보면 됐었는데, C도 꽤나 나에겐 어려웟고 D번도 어려웠던 것 같다.

A번 문제는 다음과 같다.

A. Vector Size :: https://csacademy.com/contest/round-24/#task/vector-size

이 문제는 매우매우매우 쉽기에 설명이 필요 없을 것 같다. Vector STL을 쓸 줄알면 끝이다.

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

#include <iostream> #include <cstdio> #include <vector> #include <algorithm>   using namespace std;   vector<int> vc;   int main() {     int n;     int last = 0;     scanf("%d", &n);       for (int i = 0; i < n; i++)     {         int val;         scanf("%d", &val);         if (val == 1)         {             vc.push_back(1);             last = max((int)vc.size(), last);         }         else         {             if (!vc.empty())             {                 vc.pop_back();                 last = max((int)vc.size(), last);             }         }     }       printf("%d", last);     return 0; }   //                                                       This source code Copyright belongs to Crocus //                                                        If you want to see more? click here >>

Crocus

B번 문제는 다음과 같다.

Kth Special Number :: https://csacademy.com/contest/round-24/#task/kth-special-number

문제 설명은 각 수를 비트로 봤을 때 비트단위에서 1이 연속되서 2번 이상나오면 bad number이다.

이때 bad number를 제외한 수 중, k번째 수를 구하여라가 문제이다.

비트 연산을 하는 신기한 문제였다.

어짜피 integer내에서 k번째는 나타날 것이고(비트를 나타내보면 알 수 있다.) 

적절하게 20000이라는 범위를 주어 1000번째 수가 나타나는지 확인해 보았다.

이 문제의 핵심 알고리즘은 다음과 같다.

예를 들어 16을 보자.

16은 비트가 0001 0110이다.

0001 0110이면

0000 0010 :: 2^1 = 2

0000 0100 :: 2^2 = 4 

0000 1000 :: 2^3 = 8

이런식으로 비트 단위로 한칸씩 밀어가며 1을 확인하며 풀어 낼 수 있다.

이중 포문에 브루트 포스이지만 2^0, 2^1, ... ,2^31승 수만 봄으로 현재 코드에서는 상수 시간에 끝난다.

#include <iostream>
#include <cstdio>
 
using namespace std;
int cmp[33];
int arr[20001];
int ans[20001];
int last[1001];
 
int main()
{
    int k;
    int kth = 1;
    int lth = 1;
    int cnt = 0;
    int mul = 1;
    bool chk = true;
    scanf("%d", &k);
 
    for (int i = 1; i <= 20000; i++)
        arr[i] = i;
 
    for (int i = 1; i <= 31; i++)
    {
        cmp[i] = mul;
        mul *= 2;
    }
 
    for (int i = 1; i <= 20000; i++)
    {
        for (int j = 1; j <= 31; j++)
        {
            if (arr[i] & cmp[j])
            {
                cnt++;
                if (cnt == 2)
                {
                    ans[kth++] = arr[i];
                    cnt = 0;
                    chk = false;
                    break;
                }
            }
            else
            {
                cnt = 0;
                chk = true;
            }
        }
        if (chk == true)
        {
            last[lth++] = arr[i];
            chk = true;
        }
    }
 
    printf("%d", last[k]);
    return 0;
}
 
//                                                       This source code Copyright belongs to Crocus
//                                                        If you want to see more? click here >>

C번은 쉬워 보였는데 나는 해결 방법을 찾지 못했다.

1을 한군데로 모으는 최소 swap을 찾는 것이었다.(원형 상태이고)

처음에는 [13413번] 오셀로 재배치 :: https://www.acmicpc.net/problem/13413 이 문제와 비슷해 보였으나, 좀 다른 것 같다.

D번은 이진 탐색 트리의 높이와, 노드 수가 정해졌을 때 모든 종류를 구하는 문제였다.

이 문제는 DP임을 확신하고 바로 접근하였다.

공책을 펴고 몇가지 케이스에 해당하는 개수를 헤아려보고 DP식을 만들려했지만, 생각외로 DP식이 잡히질 않았다.

정답을 확인해보니 DP식이 다음과 같다.

The answer is found in $dp_{N, H}$.

In order to compute $dp_{i,j}$, we can fix the number of nodes $k$ in the left subtree of the root. At last one the two subtrees need to have height $j-1$. We distinguish $3$ cases:

1. The left subtree has height $j-1$, the right subtree has height less than $j-1$: $dp_{i, j} += dp_{k, j-1} * \sum_{h=0}^{j-2}dp_{i-k-1, h}$ 
2. The left subtree has height less than $j-1$, the right subtree has height $j-1$: $dp_{i,j} += \sum_{h=0}^{j-2}dp_{k, h} * dp_{i-k-1, j-1}$ 
3. Both subtrees have height $j-1$: $dp_{i, j} += dp_{k, j-1} * dp_{i-k-1, j-1}$

A straight forward implementation has a complexity of $O(N^4)$, because we also need to fix $h$. We can reduce it by computing partial sums on the $dp$ columns, making the solution work in $O(N^3)$. 

아직 DP를 더 공부해야하는건지, 저걸 알 수 있는건지는 잘 모르겠지만.. 아직 갈길이 멀다는 것은 확실한 것 같다.