백준 및 코드포스

1 솔 8800등 하

https://codeforces.com/contest/1682

변명을 하자면 시험 4분 전에 일어나서 1번 풀 때 앞이 잘 안 보여서 배열 잘못 줬습니다.

그 실수 아니었으면 대충 7천 등으로 올라갈 수 있기는 한데, carrot에서 레이팅 170점이나 차이나게 부여하는 거 보니까 막 속쓰리네요

팰린드롬인 문자열을 입력받은 다음에 몇개를 지웠을 때 여전히 팰린드롬인지 맞추는 문제입니다.

지우고 나서도 여전히 팰린드롬이려면 가운데에서 지워야겠죠..

가운데에서 반복되는 문자의 개수를 출력해주세요.

#include <stdio.h>
 
int main() {
    int t;
    int arr[1000000] = {};
    scanf("%d", &t);
    char s[1000001] = {};
    while(t--) {
        int n;
        scanf("%d", &n);
        scanf("%s", s);
        for(int i = 0; i < n; i++) {
            if(s[n / 2 +i] != s[(n / 2) + 1 + i]) {
                if(n % 2 == 1) printf("%d\n", i * 2 + 1);
                else if(n % 2 == 0) printf("%d\n", (i + 1)* 2);
                break;
            }
        }
    }
}

B. AND Sorting

0부터 n -1까지 순서대로 있는 배열에서 최소 한 쌍의 숫자의 위치가 뒤바뀌었다고 합니다.

ex) 0 1 3 2 4

숫자를 한 쌍씩 짝을 지어 순서대로 sort 해야합니다.

근데 그 쌍을 지었을 때 비트연산 &을 했을 때의 값이 최소가 되도록 만들어야합니다.

제 위치에 있지 않은 값끼리 &연산을 시켜주면 정답이 됩니다.

아쉽네요

둘이서 번갈아가며 나무를 두 조각으로 자르는데, 자기 턴에 나무를 못 자르면 집니다.

나무는 자연수로만 자를 수 있고, 길이가 1이 되면 자르지 못합니다.

누가 나무 자르기 게임에서 이기는지 출력하는 문제입니다.

나무의 길이 - 1 횟수만큼 자를 수 있으니, 길이 - 1을 모두 더합니다.

그 값이 홀수면 첫 번째로 자르는 애가, 짝수면  두 번째로 자르는 애가 이깁니다.

#include <stdio.h>
int main() {
    int t;
    scanf("%d", &t);
    for(int p = 0; p < t; p++) {
        int n, temp, sum = 0;
        scanf("%d", &n);
        for(int i = 0; i < n; i++) {
            scanf("%d", &temp);
            sum += temp - 1;
        }
        if(sum % 2 == 1) printf("errorgorn\n");
        else printf("maomao90\n");
    }
}

B. I love AAAB

https://codeforces.com/contest/1672/problem/B

A(개수 무제한)B(무조건 한 개)의 문자열을 순서 상관없이 입력해서 input으로 준 문자열을 만들 수 있는지 체크하는 문제입니다.

예를 들어 AAABBAAAB를 만들어봅시다.

빨간색이 추가해준 문자열입니다.

AAAAB -> AABAAAB -> AAABBAAAB == AAABBAAAB.

이런 식으로 막무가내로 끼워넣기도 가능합니다.

1. 문자열 시작은 A, 끝은 B

2. 여태 나온 A 개수보다 B 개수가 더 많으면 안 된다. ex> AABBBAAAB (5번째에서 A 둘, B 셋으로 안 됨)

충족하면 YES 아님 NO

#include <stdio.h>
#include <string.h>
int main() {
    int t;
    char s[200001] = {};
    scanf("%d", &t);
    for(int p = 0; p < t; p++) {
        int n, temp = 0, sum = 0, no = 0;
        scanf("%s", s);
        for(int i = 0; i < strlen(s); i++) {
            if(s[i] == 'B') sum++;
            if(s[i] == 'A') temp++;
                if(sum > temp) no = 1;
        }
        if(s[strlen(s) - 1] == 'A') no = 1;
        if(no) printf("NO\n");
        else printf("YES\n");
    }
}

C. Unequal Array

https://codeforces.com/contest/1672/problem/C

#include <stdio.h>
int main() {
    int t;
    int arr[200001] = {};
    scanf("%d", &t);
    for(int i = 0; i <t; i++) {
        int n, temp = 0;
        scanf("%d", &n);
        for(int j = 0; j < n; j++) {
            scanf("%d", &arr[j]);
        }
        int count = 1, cc = 0;
        int startpoint = 0, end = 0;
        for(int j = 1; j < n; j++) {
            if(arr[j] == arr[j - 1]) {
                startpoint = j;
                break;
            }
        }
        for(int j = n - 1; j > 0; j--) {
            if(arr[j] == arr[j - 1]) {
                end = j;
                break;
            }
        }
        if(end - startpoint < 1) cc = 0;
        else if(end - startpoint <= 2) cc= 1;
        else cc = end - startpoint -1;
        printf("%d\n", cc);
    }
}

9문제(A B C D E F G I J) 맞췄습니다.

잘하시는 분들에겐 그냥 웃긴 수준일테지만, 그래도 제가 참여한 모든 대회 중에 절대적으로나 상대적으로나 순위가 제일 높아서 기분이 좋네요.

K도 확실히 풀 수 있는 문제인데, 중간에 가족들이랑 식사하고 버스타고 기차타고 하느라 시간이 없어서 그냥 못 풀었습니다.

A.

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

N명이 있을 때,어떤 사람이 숫자를 외칩니다.

그럼 그 숫자에 해당하는 사람의 번호를 출력해주면 됩니다.

k가 3보다 크면 오른쪽에 있는 거니까 오른쪽에서 찾아주고, 그것보다 작으면 왼쪽에서 찾아주면 됩니다.

오른쪽으로 돌다가 숫자가 사람수보다 커지면 1로,

왼쪽으로 돌다가 0번째 사람은 없으니까 N으로 바꿔주면 됩니다.

코드포스였으면 이런 게임을 10만번 한다고 가정해서 제 코드대로 풀면 시간초과가 나겠죠? 

#include <stdio.h>
int main() {
    int n,m,k;
    scanf("%d %d %d", &n, &m, &k);
    if(k >= 3) {
        for(int i = 3; i < k; i++) {
            m++;
            if(m > n) {
                m = 1;
            }
        }
    }
    else {
        for(int i = 3; i > k; i--) {
            m--;
            if(m == 0) {
                m = n;
            }
        }
    }

    printf("%d", m);
}

B.

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

청정수열의 개수를 구하면 됩니다.

청정수열이려면 각 정수들이 서로 붙어있어야겠죠? ex) 11223344 44332211

한 쌍의 정수를 한 묶음으로 보고, 나열하면 정답.

정답은 N!이 됩니다.

C.

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

예전 시설 - 현재 시설의 값이 가장 큰 경우를 출력하면 됩니다.

예제 2번의 경우처럼 입력을 받지 않은 경우엔 0으로 취급해주면 되겠죠?

배열 입력 후 간단한 사칙연산입니다.

D.

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

조건 1번 '단어를 재배열해 다른 단어를 만들 수 있어야 한다.' 는 알파벳의 개수를 세줘서 둘이 개수가 동일한지 확인.

조건 2번 첫 글자와 마지막 글자는 동일. s1[0], s2[0], s1[strlen(s1)], s2[strlen(s1)]가 동일한지 확인.

조건 3번 모음 제외하면 동일. 투포인터로 모음이면 넘기면서 동일한지 확인해줬습니다.

E.

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

베스킨라빈스 게임에서 준서가 무조건 이길 수 있는지 확인하는 문제입니다.

준서가 첫번째입니다.

(마지막 수 - 1) % (한 턴에 부를 수 있는 수의 개수 + 1) > 한 턴에 부를 수 있는 수의 개수 

or

(마지막 수 - 1) % (한 턴에 부를 수 있는 수의 개수 + 1) == 0 이라면 준서 패배 

나머지는 준서 승리

F.

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

이건 솔직히 노가다로 구했습니다.

스스로 브루트포스 해서 깨달았어요

#include <stdio.h>

int main() {
    int n, answer = 0;
    scanf("%d", &n);
    int temp;
    temp = 1 + n / 9;
    if(n % 9 == 0) {
        temp--;
    }
    if(n <= 9) {
        answer = 1;
    }
    else if(temp % 2 == 1) {
        answer = temp;    
    }
    else{
        answer = temp + n % 2;
    }
    printf("%d", answer);
}

G.

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

길이가 N인 수열에서 무제한으로 Swap 했을 때 숫자 위치가 다른, 그러니까

1 1 2 2의 경우, 2 2 1 1처럼 옮긴 이후에 숫자가 같은 위치에 있지 않도록 하는 문제입니다.

숫자의 범위가 10만까지밖에 안되니까 10만개의 배열로 숫자를 각각 세서

똑같은 숫자의 개수 > (N / 2) 라면 만들 수 없습니다.

예를 들어 N = 5, 그 안의 정수 2가 3개라면 

1 1 2 2 2

2 2 2 1 1

어떻게 움직여도 2 하나는 만나죠?

여기까지는 쉬운 생각이고 출력이 힘들어요.

N이 5000개 밖에 없으니까 똑같은 숫자를 만나면 넘기는 식으로 시간안에 잘 출력해줍시다.

I.

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

연속되는 알파벳이 5개인지 확인해주세요

J.

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

공책에 적어보면서 깨달았습니다.

#include <stdio.h>
int main() {
    int n;
    scanf("%d", &n);
    int arr[50001] = {};
    int temp = (n / 2);
    for(int i = 1; i <= n; i++) {
        if(i + i > 5000) break;
           arr[i + i] = i;
           arr[i + 1 + i] = temp + i + 1; {
               if(arr[i + 1] > n) {
                   arr[i + 1] = 0;
               }
           }
    }
    arr[1] = n / 2 + 1;
    for(int i = 1; i <= n ;i++) printf("%d ", arr[i]);  
}
//4 1 5 2 6 3
//4 1 5 2 6 3 7 
//3 1 4 2

주석처럼 출력될 수 있게 해주세요.

K는 쉬운 구현문제라 잘 구현해주시면 됩니다. 저는 시간이 없어서 못풀었어요.

L은 문제 이해를 잘 못했습니다. 근데 예제 보니까 느낌 와서 풀었는데 틀리더라고요.

예쁜 뱃지도 받았습니다.

문제가 간결하고 재밌었던 거 같아요.

푼 문제중에 A. 두부 두부 문제가 제일 어려웠습니다.

혹시 오류 있다면 알려주세요. 감사합니다.

너무 긴장했나?
그냥 망쳤습니다. 평소 div2 풀어보던 실력의 절반도 못했어요.
부끄러우니 제가 몇분만에 풀었는지는 공개 안 하겠습니다.
https://codeforces.com/contest/1684

Alice가 먼저 숫자 2개 순서를 바꾸고, Bob이 맨뒤에서부터 숫자 하나씩 지웁니다.
Alice는 최대한 작은 숫자가 마지막까지 살아있도록 해야합니다.
2자리인 경우에는 걍 뒤에 있는 숫자가 출력됩니다.
3자리 이상인 경우엔 무조건 최소인 숫자가 출력됩니다.
-----예-------시-------- ( '/' 이게 뒤에서 자른 거라고 생각하세요.)
132 -> 31 / 2 -> 1 / 3
321 -> 31 / 2 -> 1 / 3
312 -> 21 / 3 -> 1 / 2

숫자 길이가 3인 경우에서도 되니까 더 크면 걍 무조건 되겠죠?

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

아니 A에 코드를 너무 장황하게 짰어요.. 아 짜증나네 A랑 B는 무조건 쉽게 풀린다는 걸 전제하에 두고 문제 풀어야겠습니다.
이게 뭐하자는 건지
다음

a b c 입력해주면

이걸 만족하는 x y z를 구해주면 돼요.

조건에 a < b < c가 있습니다.
1. c가 제일 크니까 z = c 그대로 고정해둡시다.
그리고 y % c 가 b 여야 한대요.
c는 b보다 크죠?
2. y = b 그대로 고정해둡시다.
a만 남았습니다.
x % b = a 이건 만족하는데, c % x = c여야합니다.
그럼 x가 c보단 크면서 b로 나눴을 때 a가 나머지로 나오게 하면 되겠네요.
3. b * c 를 하면 c보다 큰 동시에 b에 나눠떨어집니다. 거기에 + a 하면 끝.

 #include <stdio.h>
int main() {
    int t;
    scanf("%d", &t);
    for(int i = 0; i < t; i++) {
        long long a,b,c;
        scanf("%lld%lld%lld", &a, &b, &c);
        a = a + b * c;
        printf("%lld %lld %lld\n", a, b, c);
    }
}

div 1 + div 2 다신 안 합니다. 1솔이 말인가