[코드 포스] #859 (Div. 4)

대회 주소

https://codeforces.com/contest/1807

Dashboard - Codeforces Round 859 (Div. 4) - Codeforces

문제 풀이

A번

a + b = c 또는 a - b = c 수식을 사용한 결과 a, b, c가 주어진다.
a, b, c를 통해 연산자의 부호가 +, - 인지 출력하는 문제

import sys
input = sys.stdin.readline

# input
t = int(input())
for _ in range(t):
    a, b, c = map(int, input().split())
    if a - b == c:
        print("-")
    else:
        print('+')

a - b == c 를 만족하는지, 안하는지 확인 후 결과 출력

B번

A는 짝수를 가져가고, B는 홀수를 가져간다.
A는 욕심이 많아 항상 이기고 싶어한다. 따라서 주어진 수를 재배열해, A가 항상 이기는 상황으로 만들 수 있다면 YES

import sys
input = sys.stdin.readline

def solve(n, nums):
    a, b = 0, 0
    for i in nums:
        if i % 2 == 0:
            a += i
        else:
            b += i

    if not(a > b):
        return "NO"
        
    return "YES"

# input
t = int(input())
for _ in range(t):
    n = int(input())
    nums = list(map(int, input().split()))
    print(solve(n, nums))

최종적으로 짝수의 값이 더 크다는 조건하에 짝수를 모두 앞쪽에 배치한다면 A는 항상 큰 값을 유지한다.

따라서 최종 짝수의 합과 홀수의 합을 비교하면 된다.

C번

일정 길이의 문자가 주어진다. 문자는 0 또는 1로 변환 가능하다.
모든 문자를 변환해 대칭이 되는 문자로 만들 수 있다면 YES 출력하기
이때 같은 문자는 같은 수 (0, 1)로 변환되어야 한다.

import sys
input = sys.stdin.readline

def solve(n, nums):
    visit = {}
    for i in range(n):
        c = nums[i]
        if c in visit:
            if visit[c] != (i % 2):
                return "NO"
        else:
            visit[c] = i % 2
    return "YES"
# input

t = int(input())
for _ in range(t):
    n = int(input())
    nums = list(input().strip())
    print(solve(n, nums))

홀수, 짝수 인덱스로 나누어 생각했다.

홀수 인덱스와 짝수 인덱스에 같은 문자가 존재하면 대칭을 이룰 수 없다.

visit을 딕셔너리로 선언해 해당 경우를 찾아주었다.

G번

[1] 의 배열이 주어진다. 해당 배열에서의 부분배열의 합을 새 원소로 넣을 수 있다.
즉, [1]의 부분배열의 합인 1, -> [1, 1]
[1, 1] -> [1, 1, 2] ...
이때 주어진 입력값의 배열을 만들 수 있는지 YES or NO

import sys
input = sys.stdin.readline

def solve(n, nums):
    if nums[0] != 1: return "NO"
    total = sum(nums)
    while nums:
        if nums[-1] == 1: break
        total -= nums[-1]
        if nums[-1] > total:
            return "NO"
        nums.pop()
    return "YES"

# input
t = int(input())
for _ in range(t):
    n = int(input())
    nums = list(map(int, input().split()))
    print(solve(n, sorted(nums)))

백준에서 풀어보았던 그리디 문제.. (왜인지 기억이 나지 않아서 못풀었다..)

배열을 오름차순 한 뒤, top에 존재하는 (가장 큰수)가 나머지 수의 합들보다 작다면 OK.

이를 배열의 길이가 1일때까지 반복하면 된다.

이때 마지막 원소는 항상 1이여야 한다!