코드포스 #779 (Div. 2) - A, C 풀이

 

https://codeforces.com/contest/1658

Dashboard - Codeforces Round #779 (Div. 2) - Codeforces

B는 못 풀겠습니다.

시간 재면서 풀어봤는데 A는 5분 정확히 걸렸고, C는 60분 걸렸습니다.

근데 런타임 에러도 페널티에 포함시키나요? 앞으로 배열 크기 좀 넉넉히 잡고 가야겠습니다.

배열만 잘 잡아줬어도 틀리는 횟수가 절반으로 줄어서 C는 3번만에, A는 1번 만에 맞췄겠네요..

Carrot을 통해 본 제 수준은

아마 이 분이랑 아주 비슷하지 않을까 싶네요.

A가 5분 + 10분, C 60분 + 30분 하면 대충 비슷합니다.

 

저 정도만 나오면 정말 만족스럽겠네요..

 

 

아무튼

아주 쉬운 A 부터..

아주아주 간단합니다.

대충 브론즈 3~4 정도 될 것 같은데 남자는 0, 여자는 1로 되어있는 문자열을 입력받아서

남자끼리 붙어있지 않게(00이 되지 않도록) 여자를 사이에 끼워 넣어주고, 여자는 양옆에 남자를 두지 않도록(010이 되지 않도록) 해주면 끝입니다.

 

문자열을 읽어나가면서 '00'이라면 여자 2명을, '010'이라면 여자 한 명을 끼워 넣어주면 되겠죠?

#include <stdio.h>
#include <string.h>
int main() {
    int t, n;
    char s[110] = {};
    scanf("%d", &t);
    for(int i = 0; i < t; i++) {
        int count = 0;
        scanf("%d", &n);
        scanf("%s", s);
        for(int j = 0; j < strlen(s); j++) {
            if(s[j] == '0' && s[j + 1] == '0') {
                count+=2;
            }
            else if(s[j] == '0' && s[j + 1] == '1' && s[j + 2] == '0') {
                count++;
                j++;
            }
        }
        printf("%d\n", count);
    }
}

다음 문제 C입니다.

문제는 아주아주 어려운데, 가능한 경우의 수를 직접 적어보면서 하니까 풀렸습니다.

근데 제가 누워서 휴대폰 메모장에다가 적으면서 생각해봤던 거라, 아마 종이와 펜을 들고 했으면 더 빨리 풀었을 거 같네요.

문제를 대충 해석해드리면..

 

1. 1~n까지 각각 하나씩 n개의 숫자가 들어있는 순열에서 

2. 순열의 첫 번째부터 읽어나가면서 가장 큰 값으로 갱신시켜주고

3. 갱신된 순열에서 숫자의 개수 C(i)를 확인한 후

4. 기존의 순열의 맨 뒤의 숫자를 제일 앞으로 빼주는 식으로 n번 반복했을 때

5. C(i)가 입력받은 대로 나올 수 있는지 판단하는 문제입니다.

한글인데 내용이 어렵죠?

 

 

n으로 5를 입력받았을 때를 예시로 들어보자면 

1 ~ 5까지의 순열	갱신한 순열	C(i)
2, 3, 1, 5, 4	2, 3, 3, 5 ,5	3
4, 2, 3, 1, 5	4, 4, 4, 4, 5	2
5, 4, 2, 3, 1	5, 5, 5, 5, 5	1
1, 5, 4, 2, 3	1, 5, 5, 5, 5	2
3, 1, 5, 4, 2	3, 3, 5, 5, 5	3

이런 식입니다.

n이랑 C(i) 줄테니까 불가능한 건지 가능한 건지 판별해라.라는 문제입니다.

저 조건으로 예제를 준다면 

input
1
5
3 2 1 2 3

output
YES

 

3~6까지 몇 개 만들어보다가 제가 찾은 조건이 몇 가지 있었는데요,

 

1. C(i)로 1이 1번은 무조건 나오며, 1번만 나온다.

2. C(i)는 한 번에 2 이상 커질 수 없다.

3. C(i)의 값으로 n이 나오려면 무조건 1 2 3... n 처럼 차례대로 정렬된 순열이어야 한다.

4. 3의 조건에 의해 C(i)가 n이면, 그 다음 C(i)의 값은 1이어야 한다.

 

정도가 있었습니다.

일단 빨리 풀어야 하니까 배열을 많이 만들어둔 다음에, C(i)의 값으로 1이 나온 지점을 기준으로 뒤에 값을 복붙해줘서 앞으로 진행하면서 풀었습니다. 

#include <stdio.h>
int main() {
    int t, n, arr[300001] = {}, startpoint;
    scanf("%d", &t);
    for(int i = 0; i < t; i++) {
        startpoint = -1;
        int no = 0;
        int check = 0;
        scanf("%d", &n);
        for(int j = 0; j < n; j++) {
            scanf("%d", &arr[j]);
            if(startpoint != -1 && arr[j] == 1) no = 1;
            if(arr[j] == 1) startpoint = j;
            if(arr[j] == n) check = 1;
        }
        for(int j = 0; j < n; j++) {
            arr[n + j] = arr[j];
        }
        arr[n + n] = arr[0];
        for(int j = 0; j < n; j++) {
            if(arr[startpoint + j] + 1 < arr[startpoint + j + 1]){
                no = 1;
            }
            if(arr[j] == n && arr[j + 1] != 1) {
                no = 1;
            }
        }
        if(startpoint == -1) no = 1;
        if(check == 1) {
            for(int j = 0; j < n - 1; j++) {
                if(arr[startpoint + j + 1] != arr[startpoint + j] + 1) {
                    no = 1;
                } 
            }
        }
        if(no == 1) printf("NO\n");
        else printf("YES\n");
    }
}