백준 및 코드포스

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