백준 및 코드포스

https://codeforces.com/contest/1658

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를 입력받았을 때를 예시로 들어보자면 

이런 식입니다.

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");
    }
}

안녕하세요.
백준보다 코드포스가 더 유익할 것 같아 코드포스를 하려고 합니다.
그런 김에 요즘 하루에 두어개 씩 문제를 푸는데 이 문제에 가장 시간을 오래 써서 가져와봤습니다.
근데 저 말고 다른 사람들도 많이 헤멘건지 carrot을 통해 확인해보니 풀기만 하면 그린 티어인 문제였습니다.

크롬의 확장프로그램 carrot을 통해 확인한 건데, 패널티를 엄청 먹고도 풀기만 하면 1330점 대의 mmr이 책정되는 것을 볼 수 있습니다.
코드포스도 mmr이 맞나요? 아무튼
문제는 이렇습니다.

캐릭터를 생성하는데 스텟을 찍을 겁니다.
스텟을 전부 찍었을 때 힘(srt)이 지능(int)을 초과하는 경우의 수를 출력해주면 됩니다.
ex) 힘 6 지능 4 스텟 3일 경우

로 3가지 입니다.

문제는 아주 짧고 간단하죠?

입력으로는 test case 의 횟수인 t가 먼저 입력되고,
t회만큼 힘, 지능, 추가 스텟이 입력됩니다.

저는 예외사항에 대해 경우를 나눠서 계산해줬는데요.
1. 힘에 스텟을 전부 찍었는데 여전히 힘이 지능보다 낮을 경우
ex) 힘 5 지능 10 스텟 5 이면 힘에 전부 찍어도 10/ 10으로 힘이 높지 않습니다.

2. 스텟을 추가로 찍을 수 없지만 이미 힘이 지능보다 클 경우 정도입니다.
ex) 힘 5 지능 4 스텟 0이면 이미 힘이 높습니다. -> 경우의 수는 1

기본적으로 이 글을 보고 계시고 제 풀이 방법이 마음에 들어서 읽고 계신다면 위의 내용은 이미 다 알고 계실 것이고 저랑 같은 부분에서 막히지 않을까 생각이 드는데요, 제가 막힌 부분에 대해서 설명드릴게요.

힘이 지능+스텟 보다 높을 때의 계산이 문제였습니다.
ex) 힘 5 지능 0 스텟 3

지능+ 스텟 < 힘
일 경우 경우의 수는 스텟 + 1이 됨이 당연합니다. 이 부분에 신경 써주시면 풀 수 있을 겁니다.
저는 뭐에 홀렸는지 위와 같은 상황에서 스텟 * 2를 출력해주고 있어서 계속 틀렸습니다.
중간에 뭘 틀렸는지 모르겠어서 계속 보고 한국어로 검색도 해봤는데 나오는게 없어서 제가 적었습니다.

처음에 이 실수만 안 하고 빠르게 제출했으면 민트 커트라인인 거로 보았을 때 확실히 사람들이 실수를 많이 한 문제인 것으로 판단되네요.
수고하세요

#include <stdio.h>
int main() {
    int s,i,e;
    int n;
    scanf("%d", &n);
    for(int p = 0; p < n; p++) {
        int count = 0; //경우의 수를 담을 변수입니다.
        scanf("%d %d %d", &s, &i, &e);
        if(s + e <= i) count = 0;//힘에 스텟을 전부 찍었는데도 지능보다 낮으면 경우의 수는 0
        else if(s + e > i) {
            count += (s + e - i) / 2;
            if((s + e - i) % 2 == 1) count++;
            if(s > e + i) {
                count += e;
            }
        }
        if(e == 0 && count > 0) count = 1;
        if(e == 0 && s > i) count = 1; //추가 스텟이 없는데 이미 힘이 지능보다 클 경우 1
        else if(count > e * 2) count = e + 1; //이 부분을 제대로 처리 못했습니다.
        printf("%d\n", count);
    }
}

https://www.acmicpc.net/problem/15927

안녕하세요. 오랜만에 한 번에, 실수 없이, 빠른 시간에 맞은 골드 문제입니다.

문제는 간단합니다.

문자열을 입력받아서 팰린드롬이 아닌 부분의 길이를 출력하면 되는 것입니다.

예제 1번 보시면 ABCBA는 팰린드롬이죠?

앞이나 뒤에서 A를 빼면 팰린드롬이 아닙니다.

AABBAA 팰린드롬, 앞이나 뒤에서 빼면 아닙니다.

감이 오셨나요? 

일단 제일 앞, 뒤에서 부터 하나씩 짝을 지어서 문자를 검사해줍니다.

이렇게 검사를 했을 때 전부 똑같다면 팰린드롬이겠죠.

저는 문자열의 길이 / 2 만큼 검사를 해줬는데요, 단어가 홀수인 경우에도 문제가 되지 않습니다.

어차피 앞에서부터 전부 똑같았다면 가운데의 문자는 어떻든 팰린드롬이기 때문이죠.

만약 팰린드롬이라면 앞이나 뒤에서 하나만 빼줘도 팰린드롬이 아니게 됩니다. 어떤 팰린드롬도 이 공식은 적용됩니다.

이렇게 해서

팰린드롬이라면 : 문자열 길이 - 1

팰린드롬이 아니라면 : 문자열 길이

전부 똑같다면 : -1

을 출력해주면 됩니다.

반례 알려드릴게요

ABABABABA
8

ABABABAB
8

ABCABCABC
9

BBBBBBBBBBBBBBBBBABBBBBBBBBBBBBBBBBABBBBBBBBBBBBBBBBB 
52

BBBBBBBBBBBBBBBBBABBBBBBBBBBBBBBBBB 
34

BBBBBBBBBBBBBBBBBABBBBBBBBBBBBBBBBBB 
36

제 코드 알려드릴게요

#include <stdio.h>
#include <string.h>

int main() {
    char s[500000] = {};
    int check = 0;
    scanf("%s", s);
    for(int i = 0; i < strlen(s)/2; i++) {
        if(s[i] != s[strlen(s) - 1 - i]) {
            check = 1;
        }
    }
    int same = 1;
    for(int i = 0; i < strlen(s) - 1; i++) {
        if(s[i] != s[i + 1]) same = 0;
    }
    if(same == 1) printf("-1");
    else if(check == 1) printf("%lu", strlen(s));
    else if(check == 0) printf("%lu", strlen(s) - 1);
}

안녕하세요 황지원입니다.

한 달 전에 정렬하는 법 몰라서 못 풀었던 문제 오늘 풀었습니다.

실버 4의 문제인데요, 푸는 방법은 이렇습니다.

n개의 정수 A[N]을 정렬해준 다음에

m개의 정수가 A안에 있는지 찾아주기만 하면 되는 간단한 문제입니다.

실버 4인데 이분탐색 안 쓸 줄 알고 알고리즘 고민하다가 설마 이분탐색 쓰나 봤더니 정말 이분탐색 쓰던군요.

유의하셔야 할 점은 딱히 없습니다.

정수의 범위가 -2^31 ~ 2^31 이라는 점에 유의해서 int 형이 아닌 long long을 써보세요.

반례 드리겠습니다.

4                      
2147483647 10 -2147483640 0 
5
0 0 0 2147483647 9 

정답

1
1
1
1
0

5
0 0 0 0 0
5 
1 1 1 1 0

정답

0
0
0
0
1

1
1
1
1

정답

1

#include <stdio.h>
void quickSort(long long arr[], int L, int R) {
      int left = L, right = R;
      int pivot = arr[(L + R) / 2];
      int temp;
      do
      {
        while (arr[left] < pivot)
            left++;
        while (arr[right] > pivot)
            right--;
        if (left<= right)
        {
            temp = arr[left];
            arr[left] = arr[right];
            arr[right] = temp;
            left++;
            right--;
        }
      } while (left<= right);
    if (L < right)
        quickSort(arr, L, right);
 
    if (left < R)
        quickSort(arr, left, R);
}
int main() {
    long long arr[100000] ={}, brr[100000] = {};
    long long n, m, a;

    scanf("%lld", &n);
    for(int i = 0; i < n; i++) {
        scanf("%lld", &arr[i]);
    }

    scanf("%lld", &m);
    for(int i = 0; i < m; i++) {
        scanf("%lld", &brr[i]);
    }
    quickSort(arr, 0, n - 1);
    for(int i = 0; i < m; i++) { //이분탐색 구간입니다.
        long long end = n-1, first = 0;
        for(int j = 0; j < 20; j++) {
            if(arr[(end + first)/ 2] > brr[i]) {
                end = (end + first) / 2;
            }
            else first = (end + first) / 2;
        }
        if(arr[first] == brr[i] || arr[end] == brr[i]) {
        printf("1\n"); //줄바꿈에 유의하세요
        }
        else printf("0\n"); //줄바꿈에 유의하세요
    }
}