[Csacademy] Csacademy Round #32 이야기

이번 시험은 A, B, C 3문제를 해결함으로써 1429(+40)점으로 마무리하였다.

이번 라운드는 너무 따져야 할 내용이 많았던 것 같고 정교함이 필요했던 것 같다.

A. Next Dance Move :: https://csacademy.com/contest/round-32/task/next-dance-move/

간단하다. 1,2,3,1,2,3,1,2,3,4 배열에서 k번째 수를 찾아야한다.

%를 쓰면 해결되는 문제이다.

시간 복잡도는 O(1) 이다.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17

#include <iostream> #include <cstdio>   using namespace std;   int arr[11] = { 1,2,3,1,2,3,1,2,3,4 }; int main() {     int n;     scanf("%d", &n);       printf("%d", arr[((n - 1) % 10)]);     return 0; }   //                                                       This source code Copyright belongs to Crocus //                                                        If you want to see more? click here >>

Crocus

B. Food Pairing :: https://csacademy.com/contest/round-32/task/food-pairing/

프로그래머가 총 2가지 음식을 먹고싶어하는데 그 2가지 음식을 현재 남은 재료를 이용하여 최대 몇개를 만들 수 있는지 확인하는 문제이다.

문제 설명자체도 매우 어렵다. 물론 풀어서 이제는 이해가 되지만 문제를 이해하는 동안에는 매우 고통스러웠던 것 같다.

예제 인풋을 보면 다음과 같다.

2
10 10
3
2 3
3 1
1 5

즉 (2,3) (3,1)을 각각 2개씩 만들면 필요한 재료가 4 + 6, 6 + 2로 10, 8이 되기에 10, 10을 넘지 않아 만족하게 된다.

결국 답이 2이다.( (1,5)를 쓰면 최대 2라는 답이 나올 수 없게된다. )

이제 문제를 접근해보자.

아래 주어진 요구 재료를 pair로 짝지어 모두 더해준다.

즉 2,3과 3,1을 더해주고 2,3과 1,5를 더해주고 3,1과 1,5를 더해준다. 이것이 가능한 이유는 M제한이 512밖에 안되기 때문에

511C512(조합)로 가능하다.

그 후 pair에서 최대 몇개의 음식을 만들 수 있는지 모두 비교를 해주면 답을 낼 수 있다.

이때 조심해야하는 것은 모든 음식을 만들 때 요구되는 재료가 0일수 있다. 이때 0으로 나누어지는 것을 조심하면 된다.

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <limits.h>
 
using namespace std;
 
int arr[40];
int want[600][40];
int tmp[40];
 
int main()
{
    int n;
    scanf("%d", &n);
 
    for (int i = 0; i < n; i++)
        scanf("%d", &arr[i]);
 
    int m;
    scanf("%d", &m);
 
    for (int i = 0; i < m; i++)
        for (int j = 0; j < n; j++)
            scanf("%d", &want[i][j]);
 
    int finalget = 0;
    for (int i = 0; i < m - 1; i++)
    {
 
        bool chk = false;
        for (int t = 0; t < n; t++)
            if (want[i][t] != 0)
            {
                chk = true;
                break;
            }
        if (!chk)
            continue;
 
        for (int j = i + 1; j < m; j++)
        {
 
            bool chk = false;
            for (int t = 0; t < n; t++)
                if (want[j][t] != 0)
                {
                    chk = true;
                    break;
                }
            if (!chk)
                continue;
 
            int get = INT_MAX;
 
            for (int k = 0; k < n; k++)
            {
                
                tmp[k] = want[i][k] + want[j][k];
 
                if (tmp[k] != 0)
                {
                    tmp[k] = arr[k] / tmp[k];
 
                    get = min(get, tmp[k]);
                }
            }
 
            finalget = max(finalget, get);
        }
    }
 
    printf("%d", finalget);
    return 0;
}
 
//                                                       This source code Copyright belongs to Crocus
//                                                        If you want to see more? click here >>

C. Subarray Partition :: https://csacademy.com/contest/round-32/task/subarray-partition/

극악의 해석이 필요한 문제였다.. 외국인들도 심지어 해석하느라 문제를 못풀었다고 할 정도였다.

문제 의미는 다음과 같다.

주어진 배열에서 부분배열을 만들 때 항상 같은수는 같은 부분배열에 있어야한다. 

이때 최대로 많이 만들 수 있는 부분배열 수를 구해야한다.

예시를 바로 보면 쉽다.

Input	Output
4 1 2 2 1	1
4 1 2 3 4	4
4 1 1 2 2	2

1번은 1 2 2 1이니 1과 1이 같은 부분배열이 되기 위해서는 {1, 2, 2, 1}이 답이어야 한다. 따라서 답은 1

2번은 1 2 3 4이니 {1} {2} {3} {4} 이렇게 서로 따로 있으면 된다. 따라서 답은 4

3번은 1 1 2 2이니 {1 1} {2 2}가 되면 된다. 따라서 답은 2이다.

이 간단하게 생긴 문제를 이해하는데 정말 시간을 다써서 너무 아쉽다.

투포인터를 생각하며 풀면 되는데 이때 왼쪽 포인터는 움직이지 않고 오른쪽 포인터만 움직이도록 설정하여 풀면 된다.

fidx를 두어 왼쪽을 고정시키고 eidx를 두어 fidx가 가진 수의 마지막위치가 어딘지 eidx가 가지게 된다.

그리고 fidx와 eidx 사이에 수를 점검하는 teidx를 두고 eidx보다 teidx가 더 큰 index를 가지게 된다면 eidx를 갱신해준다.

최종적으로 i는 eidx + 1을 해주며 그다음 인덱스부터 검사해주도록 하면 최대 부분 배열을 만들 수 있다.

#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
 
using namespace std;
 
int arr[100002];
vector<int> vc[100002];
 
int main()
{
    int n;
    scanf("%d", &n);
 
    int maxNum = 0;
    for (int i = 0; i < n; i++)
    {
        scanf("%d", &arr[i]);
        vc[arr[i]].push_back(i);
 
        maxNum = max(maxNum, arr[i]);
    }
 
    int cnt = 0;
    for (int i = 0; i < n; i++)
    {
        int num = arr[i];
        int fidx = vc[num][0];
        int eidx = vc[num][vc[num].size() - 1];
 
        for (int j = fidx; j < eidx; j++)
        {
            int tnum = arr[j];
            int teidx = vc[tnum][vc[tnum].size() - 1];
 
            if (eidx < teidx)
                eidx = teidx;
        }
        cnt++;
        i = eidx + 1;
        i--;
    }
    printf("%d", cnt);
 
 
    return 0;
}
 
//                                                       This source code Copyright belongs to Crocus
//                                                        If you want to see more? click here >>