백준 및 코드포스

A. XOR Mixup

n - 1 개의 정수를 모두 xor연산한 숫자가 추가된 후 n개의 정수를 섞었을 때, 추가된 하나의 숫자를 찾는 문제입니다.

그냥 n개 중에 아무 숫자나 출력하면 정답입니다.

#include <stdio.h>
using namespace std;
int main() {
int n, m;
int t;
scanf("%d", &t);
    while(t--) {
        scanf("%d", &n);
        for(int i = 0; i < n; i++) {
            scanf("%d", &m);
        }
        printf("%d\n", m);
    }
}

B. Rising Sand

 1 < 𝑖 < 𝑛 인 동시에 𝑎𝑖 > 𝑎𝑖−1 + 𝑎𝑖+1 인 모든 i번째 모래 더미는 too tall 이라고 합니다.

k개의 연속된 모래 더미의 크기를 동시에 1씩 무한 번 추가할 수 있을 때, 만들 수 있는 too tall 모래 더미의 개수를 출력하면 됩니다.

k가 1이라면 원하는 모래더미만 골라서 크기를 키울 수 있기 때문에

하나 건너 하나씩 too tall하게 만들 수 있습니다.

k가 1 일 경우 정답은 (n - 1) / 2

k가 2 이상인 경우 이미 too tall 하지 않을 경우 too tall 하게 만들 수 없습니다.

기존의 too tall 한 모래 더미의 수를 세어주면 정답입니다.

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

C. 3SUM Closure

arr[i] + arr[j] + arr[k] 의 값이 배열에 없을 경우 NO, 모든 경우에서 있을 경우 YES를 출력해주면 됩니다.

양수가 3개 이상이면 양수끼리 3개를 더할 경우 무조건 더해진 3개의 양수의 값보다 더 큰 양수가 나오기 때문에 무조건 no 입니다.

음수가 3개 이상일 경우에도 마찬가지입니다.

0은 10000개가 있으나 3개가 있으나 결과가 동일하므로 0의 개수가 3 이상일 경우 3으로 퉁쳐주었습니다.

그리고 남은 값들 끼리 브루트포스를 돌려주면 됩니다.

#include <stdio.h>
int main() {
int n, m;
int arr[1000000] = {};
int ans[10] = {};
int t;
scanf("%d", &t);
while(t--) {
    int plus = 0, minus = 0, zero = 0, one = 0, no = 0;
    scanf("%d", &n);
    for(int i = 0; i < n; i++) {
        scanf("%d", &arr[i]);
        if(arr[i] > 0) plus++;
        else if(arr[i] < 0) minus++;
        else if(arr[i] == 0) zero++;
    }
    if(plus > 2) no = 1;
    else if(minus > 2) no = 1;
 
    else {
        for(int i = 0; i < n; i++) {
            if(arr[i] > 0 || arr[i] < 0) {
                ans[one] = arr[i];
                one++;
            }
        }
        if(zero > 3) zero = 3;
        for(int i = 0; i < zero; i++) {
            ans[one] = 0;
            one++;
        }
        for(int i = 0; i < one; i++) {
            for(int j = i + 1; j < one; j++) {
                for(int k = j + 1; k < one; k++) {
                    no = 1;
                    for(int z = 0; z < one; z++) {
                        if(ans[i] + ans[j] + ans[k] == ans[z]) no = 0;
                    }
                    if(no == 1) goto E;
                }
            }
        }
    }
    E:
    if(no) printf("NO\n");
    else printf("YES\n");
 
}
}

아 진짜 아쉽네요 E에서 뭐가 틀린 건지 한참 헤멨는데 int를 long long으로 바꾸니까 바로 AC 받았습니다.

그것만 신경 써줬으면 1350 정도 퍼포 나왔을텐데 진짜 아쉽네요..

세네판 정도 안에 그린 찍고 싶었는데 ㅋㅋ 안 될 것 같네요

A. Print a Pedestal (Codeforces logo?)

가운데가 제일 길쭉하고 왼쪽이 그 다음, 오른쪽이 그다음으로 길도록 해주는 단순 구현 문제입니다.

#include <stdio.h>

int main() {
int n, t;
scanf("%d", &t);
while(t--) {
    scanf("%d", &n);
    int first = n / 3 + 1;
    if(n % 3 != 0) first++;
    int second = n - first;
    second /= 2;
    second++;
    int third = n - first - second;
    printf("%d %d %d\n", second, first, third);
}
}

B. Array Decrements

이번 코포는 B 때문에 망했다고 해도 과언이 아닌..

#include <stdio.h>

int main() {
int n,m, t;
int arr[1000000] = {};
int brr[1000000] = {};
scanf("%d", &t);
while(t--) {
    scanf("%d", &n);
    int temp = 0,NO = 0,no = 0;
    for(int i = 0; i < n; i++) {
        scanf("%d", &arr[i]);
    }
    for(int i = 0; i < n; i++) {
        scanf("%d", &brr[i]);
        if(arr[i] < brr[i]) NO = 1;
    }
    for(int i = 0; i < n; i++) {
            if(temp < arr[i] - brr[i]) temp = arr[i] - brr[i];
    }
    if(temp == 0) temp = arr[0] - brr[0];
    for(int i = 0; i < n; i++) {
        arr[i] -= temp;
    }
    for(int i = 0; i < n; i++) {
        if(arr[i] != brr[i]) {
            no++;
            if(brr[i] == 0 && arr[i] <= 0) no--;
        }
    }
    if(no || NO) printf("NO\n");
    else printf("YES\n");
}
}

이렇게 어렵게 푸는 것도 맞는지도 모르겠습니다 사실..

여태 코포 몇판 안 해봤지만 중간에 문제 하나 막히면 거기서 말리기 시작하는 타입인 거 같아요 저는

일 끝나기 전에 다음 task 주면, task 끝낸 시간의 간격 출력.

일 끝나고 난 후에 다음 task 주면 task 준 시간과 끝낸 시간의 간격 출력.

푸는 데에 5분도 안 걸렸습니다.

#include <stdio.h>
int main() {
int n, t;
long long arr[300000] = {};
long long brr[300000] = {};
scanf("%d", &t);
while(t--) {
    scanf("%d", &n);
    for(int i = 0; i < n; i++) {scanf("%lld", &arr[i]);
    }
    for(int i = 0; i < n; i++) {scanf("%lld", &brr[i]);
    }
    printf("%lld ", brr[0] - arr[0]);
    for(int i = 1; i < n; i++) {
        if(arr[i] < brr[i - 1]) printf("%lld ", brr[i] - brr[i - 1]);
        else printf("%lld ", brr[i] - arr[i]);
    }
    printf("\n");
}
}

D. Black and White Stripe

문자열에서 0~k-1 의 문자열 안에 W가 얼마나 들어있는지 찾고

앞으로 한 칸씩 나가면서 가장 적은 값 출력.

엄청 쉬운 문제인데 구현 실수해서 2번이나 틀렸습니다.

근데 이건 제 실력이 부족한 탓이에요

#include <stdio.h>
#include <algorithm>

int main() {
int n,m, t;
char s[300000] = {};
scanf("%d", &t);
while(t--) {
 scanf("%d", &n);
 scanf("%d", &m);
 scanf("%s", s);
 int count = 0, min = 10000000;
 for(int i = 0; i < m; i++) {
     if(s[i] == 'W') count++;
 }
 if (min > count) min = count;
 for(int i = 0; i < n - m; i++) {
     if(s[m + i] == 'W') count++;
     if(s[i] == 'W') count--;
     if(min > count) min = count;
 }
 printf("%d\n", min);
}
}

E. Price Maximization

맨 처음에 각각 물건 입력받으면서 k로 나눈 값 더해주고,

나머지는 모아서 배열에 담은 다음에 작은놈들끼리 짝지어주면서 짝 맞으면 더해주는 식으로 짰습니다...

구현까지도 괜찮았는데 long long을 쓰는 걸 깜빡했네요

𝑎𝑛은 10억까지도 가능하니까 당연히 long long인데 이걸 뭔 생각으로 int로 출력하려 했는지..  앞으로 

#define int long long 쓰겠습니다 짜증나서..

#include <stdio.h>

int main() {
int n,m, t;
int k[1001] = {};
scanf("%d", &t);
while(t--) {
    scanf("%d%d", &n, &m);
    long long temp = 0;
    long long ans = 0;
    for(int i = 0; i < n; i++) {
        scanf("%lld", &temp);
        ans += temp / m;
        k[temp % m]++;
    }

    int end = m, first = 1;
    
    for(int i = 0; i <= m; i++) {
        for(int j = m - i; j <= m; j++) {
                if(i == j) {
                    ans+= k[i] / 2;
                    k[i] %= 2;
                    continue;
                }
                if(k[i] > 0 && k[j] > 0) {
                if(k[i] > k[j]) {
                    int temp = k[j];
                        ans += k[j];
                    k[i] -= temp;
                    k[j] -= temp;
                }
                else {
                    int temp = k[i];
                    ans += k[i];
                    k[i] -= temp;
                    k[j] -= temp;
                }
                                    //printf("%d %d\n", k[i], k[j]);
            }
        }
    }
    for(int i = 0; i < 1000; i++) {
        k[i] = 0;
    }
    printf("%lld\n" , ans);
}
}

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

간결한 그리디 문제입니다.

저울 문제를 풀 경우 코드포스의 이 문제도 1분컷으로 쉽게 풀 수 있습니다.

괜찮은 예제에 대한 설명을 읽으시면 바로 이해가 갈 거라고 예상합니다.

1, 2, 4, 8, 16의 추를 가진 경우입니다.

1 - 가능 ( 1 )

2 - 가능 ( 2 )

3 - 가능 ( 2 + 1 )

4 - 가능 ( 4 )

5 - 가능 ( 4 + 1 )

6 - 가능 ( 4 + 2 )

7 - 가능 ( 4 + 2 + 1 )

8 - 가능 ( 8 )

.

.

32 - 불가능 (다 더해도 31입니다.)

위의 예시에서 32는 앞의 숫자를 모두 더해도 만들 수 없는 수였기 때문에 만드는 것이 불가능했습니다.

여태까지 모든 추 무게의 합 + 1보다 큰 값이 다음 추의 무게로 왔을 때는 그다음 추의 값을 측정할 수 없습니다.

위의 경우, 정답은 (이전까지의 모든 추의 무게 + 1)입니다.

위의 경우가 없을 시, 정답은 (모든 추의 무게의 합 + 1)입니다.

반례랑 제 코드 알려드리겠습니다.

5
1 2 4 8 16

answer : 32


900
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 

answer : 901

1
1

answer : 2

1
2

answer : 1

#include <stdio.h>
#include <algorithm>
int main() {
    int sum = 0, n;scanf("%d", &n);
    int arr[1000] = {};
    for(int i = 0; i < n; i++) {
        scanf("%d", &arr[i]);
    }
    std::sort(arr, arr+n); //정렬은 필수입니다.
    for(int i = 0; i < n; i++) {
        if(arr[i] <= sum +1) sum +=arr[i];
        else break;
    }
    printf("%d", sum+1);
}

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

문제 자체는 어렵지 않았는데 시간제한이 너무 빡빡했습니다.

몰랐는데 strlen 함수가 시간을 엄청나게 잡아먹더라고요. 변수에다가 strlen 값을 미리 저장시켜두고 써먹어야겠습니다.

이거 때문에 2~30분은 버렸네요.

제가 푼 문제 풀이 로직은 이렇습니다.

먼저 알파벳의 개수를 세어줄 answer 배열을 준비합니다.

1. S를 앞에서부터 읽어나가며 T에 동일한 문자가 있는지 찾습니다.

2. T[0]과 동일하다면 answer[T[0]]++,  첫 번째 이후의 문자와 동일하다면 answer[T[j - 1]]의 값과 비교해서 answer[T[j]] 가 더 작다면 answer[T[j]]++.

answer[T의 마지막 알파벳] 이 정답입니다.

ex) waawa wa 의 경우 위의 연산을 마치면 w 2개 a 2개로 정답은 2가 됩니다.

      aaassss sa 의 경우 위의 연산을 마치면 s 4개 a 0개로 정답은 0이 됩니다.

밑에 반례와 코드입니다.

waaaawawawawwwaaaaaawwawawwawawwaaaawa
aw

15


tasdfjasdfletllelteeelteletelteeelteltleltelltelltelellelelelllteltleltlqwereltlqwerleqwerlellelqwereeeteqwerlqwerltltelasdfkasdfeowijqjofiajsdnfvznxnnftlelteltleltellteltle
tle

23


jiwon
jiwon

1


goodgooddogbaaaaagood
god

3

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

int main() {
    char s[1000011] = {}, t[26] = {};
    int answer[150] = {};
    scanf("%s %s", s, t);
    int a = strlen(s), b = strlen(t);
    for(int i = 0; i < a; i++) {
        for(int j = 0; j< b; j++) {
            if(s[i] == t[0]) {
                answer[t[0]]++;
                break;
            }
            else if(s[i] == t[j] && answer[t[j]] < answer[t[j - 1]]) {
                answer[t[j]]++;
                break;
            }
        }
    }
    printf("%d", answer[t[b - 1]]);
}