- 총 12문제이고 다 푸는데 2시간 걸렸다. 문제가 쉬운 거에 비해 구현 속도가 느려서 아쉽다

제4회 AGCU Cup

문제 출처: 정올 21041번

- $s$에 각 문자가 있는지 판단하고 존재하면 그에 맞는 점수를 획득하면 된다

def solution():
    s = input().rstrip()
    score = 0
    if "A" in s:
        score += 1
    if "G" in s:
        score += 2
    if "C" in s:
        score += 4
    if "U" in s:
        score += 8
    print(score)


solution()

^9(u

문제 출처: 정올 21042번

- 기존 문자열에서 ^9(u의 개수를 세자. 그리고 ^, 9, (, u를 더미 문자로 바꾼 뒤 v, 6, ), n을 각각 ^, 9, (, u로 대체하고 문자열을 뒤집자. 이 문자열에서 ^9(u의 개수를 센 뒤 기존 것과 비교하면 된다

def solution():
    N = int(input())
    s = input().rstrip()
    t = "^9(u"
    original = len(s.split(t)) - 1
    s = s.replace("^", "@")
    s = s.replace("v", "^")
    s = s.replace("9", "@")
    s = s.replace("6", "9")
    s = s.replace("(", "@")
    s = s.replace(")", "(")
    s = s.replace("u", "@")
    s = s.replace("n", "u")
    s = s[::-1]
    reverse = len(s.split(t)) - 1
    if original == reverse:
        print("SAME")
    elif original < reverse:
        print("YES")
    else:
        print("NO")


solution()

- 에디토리얼 보니까 더 좋은 방법이 있다. 문자열을 명시적으로 뒤집는 대신 n)6v의 개수를 세는 것이다. 이는 뒤집은 문자열에 존재하는 ^9(u의 개수와 동일하다

제4회 AGCU Cup Recovery

문제 출처: 정올 21043번

- 하드 코딩해서 풀었다. 문자열의 길이가 $4$여야 함에 주의하자

def solution():
    N = int(input())
    strings = ["AAAA", "GGGG", "AAAG", "CCCC", "AAAC", "GGGC", "AAGC", "UUUU", "AAAU", "GGGU", "AAGU", "CCCU", "AACU", "GGCU", "AGCU"] 
    print(strings[N - 1])


solution()

내일은 월요일

문제 출처: 정올 21044번

- $d$를 $7$로 나눈 나머지의 개수를 저장하자. 이 중 최댓값을 가지는 나머지를 출력하면 된다. 단, 답이 $0$인 경우 $7$을 출력해야 한다

def solution():
    N = int(input())
    remainders = [0] * 7
    for _ in range(N):
        d = int(input())
        remainders[d % 7] += 1
    i = max(range(7), key=lambda x: remainders[x])
    if i == 0:
        i = 7
    print(i)


solution()

창의적인 문제

문제 출처: 정올 21045번

- 전투에서 승리한 쪽은 다른 전투에도 참여할 수 있으므로 항상 모든 창을 전투에 참여시키는 게 이득이다

- 대창 마을 입장에서 최악의 경우는 대방어 마을의 모든 방패를 전투에 참여시키는 것이다. 따라서 모든 창의 공격력 합이 모든 방패의 방어력 합보다 크면 정답은 YES이고 아니면 NO이다

def solution():
    N, M = map(int, input().split())
    A = list(map(int, input().split()))
    B = list(map(int, input().split()))
    if sum(A) > sum(B):
        print("YES")
    else:
        print("NO")


solution()

사랑의 흉터

문제 출처: 정올 21046번

- 사랑의 상처 문제 해설로 갈음하겠다

수열과 게으른 쿼리

문제 출처: 정올 21047번

- $2$번 쿼리가 들어올 때마다 수열의 합을 출력하면 된다. $1$번 쿼리에 의해 수열의 합은 $c\cdot (r - l + 1)$만큼 변화하며 이는 $O(1)$이다. 따라서 전체 알고리즘의 시간 복잡도는 $O(N+Q)$이다

def solution():
    N, Q = map(int, input().split())
    array = list(map(int, input().split()))
    total = sum(array)
    for _ in range(Q):
        query = input().split()
        if len(query) == 1:
            print(total)
        else:
            _, l, r, c = map(int, query)
            total += (r - l + 1) * c


solution()

금메달은 사실 은메달이야!!

문제 출처: 정올 21048번

- 연속된 동일한 문자는 하나로 압축하자. 모두 은메달로 바꾸기 위해 앞에서부터 마법을 시전해 나가야 한다. 압축된 문자열의 길이를 $m$이라 하자

- 홀짝성을 이용해 문제를 해결할 수 있으며 압축된 문자열의 첫 번째 문자가 G이고 $m$이 홀수라면 정답은 $m$이다. 짝수라면 $m-1$이다

- 만약 압축된 문자열의 첫 번째 문자가 S이고 $m$이 홀수라면 정답은 $m-1$이다. 짝수라면 $m$이다

from itertools import groupby


def solution():
    N = int(input())
    s = input().rstrip()
    groups = [key for key, _ in groupby(s)]
    m = len(groups)
    if groups[0] == "G":
        if m % 2 == 1:
            answer = m
        else:
            answer = m - 1
    else:
        if m % 2 == 1:
            answer = m - 1
        else:
            answer = m
    print(answer)
    

solution()

로봇 팔 조립

문제 출처: 정올 21049번

- $(0,0)$과 $(X, Y)$ 사이의 거리를 $d$라 하자. $(L_1 + L_2)^2 < d^2$이면 목표 좌표가 너무 멀리 떨어져서 닿을 수 없다. 반대로 $|L_1 - L_2| > d^2$이라면 목표 좌표가 너무 가까워서 닿을 수없다

def solution():
    X, Y = map(int, input().split())
    L1, L2 = map(int, input().split())
    ds = X**2 + Y**2
    if (L1 + L2)**2 < ds or ds < (L1 - L2)**2:
        print("NO")
    else:
        print("YES")


solution()

Double Up

문제 출처: 정올 21050번

- 우선 $N$이 짝수라고 하자. $a=1, b=2$부터 시작하자. 탐지기를 작동했을 때 결괏값이 $1$이라면 둘 중 한 곳에 보물이 숨겨져 있다

- 구역 $a$와 이미 보물이 없는 구역으로 확정된 곳에서 탐지기를 작동시키자. 탐지기가 울리면 구역 $a$에 보물이 숨겨져 있는 것이며 그렇지 않다면 구역 $b$에 보물이 숨겨져 있는 것이다

- 만약 탐지기를 작동했을 때 결괏값이 $0$이라면 두 구역 $a,b$에 보물이 없는 것이다. $a,b$를 $a+2, b+2$로 갱신하여 탐색을 재개하자. 단, $a=N-1, b=N$이라면 보물이 $N-1, N$ 구역 중 한 곳에 있는 것이 확정이니 이를 확인하기 위해 탐지기를 작동할 필요는 없다. 바로 구역 $N-1$과 구역 $N$ 중 어디에 보물이 숨겨져 있는지 확인하자. 최악의 경우에도 $\left\lceil\frac{N}{2}\right\rceil$번만 탐지기를 작동시키면 보물을 찾을 수 있다

- 이제 $N$이 홀수라고 하자. 이 경우 탐지기를 최대 $\left\lceil\frac{N}{2}\right\rceil$번 작동시킬 수 있다. 예컨대 $N=7$이라면 탐지기를 최대 $4$번 작동시킬 수 있다

- 보물이 있는 구역을 찾는 방법은 $N$이 짝수일 때와 거의 동일하다. 단, $a=N, b= N+1$이 됐다면 보물은 $N$ 구역에 존재함에 유의하자

def solution():
    N = int(input())
    a, b = 1, 2
    no_treasure = N
    while a < N - 1:
        print("?", a, b, flush=True)
        result = int(input())
        if result == 1:
            break
        a += 2
        b += 2
        no_treasure = 1
    if a == N:
        print("!", N)
        return
    print("?", a, no_treasure, flush=True)
    result = int(input())
    if result == 1:
        print("!", a)
    else:
        print("!", b)


solution()

천막 세우기

문제 출처: 정올 21051번

- 기본적으로 $a + b > c$여야 삼각형이 만들어짐에 주목하자. 이를 정리하면 $c - b < a$이며 이는 두 철근의 길이 차이가 $a$ 미만이라는 것이다

- $d = c - b$라고 하자. 그럼 $c = b + d$이다. 피타고라스 정리에 따라 $a^2 + b^2 = c^2$이므로 이를 이용하면 $a^2 + b^2 = (b + d)^2 = b^2 + 2bd + d^2$이므로 $b = \frac{a^2 - d^2}{2d}$이다

- 여기서 $a$와 $d\,(>0)$는 상수이므로 $O(1)$에 $b$를 구할 수 있고 $c = b+ d$이다

- 가능한 $d$의 개수는 $a - 1$이므로 전체 알고리즘의 시간 복잡도는 $O(a)$이며 $a$는 최대 $10^9$이지만 연산이 가벼우므로 제한 시간 내에 통과할 수 있을 것 같다

def solution():
    a = int(input())
    a_s = a**2
    diff = 0
    for d in range(1, a):
        d_s = d**2
        numerator = (a_s - d_s)
        denominator = 2 * d
        if numerator % denominator != 0:
            continue
        b = numerator // denominator
        print(b, b + d)
        return


solution()

사랑의 상처

문제 출처: 정올 21052번

- 색깔별로 장미 개수가 균등해야 상처의 개수가 최소가 된다. 꽃의 개수가 $s$일 때 상처의 개수는 $\frac{s(s - 1)}{2}$이다. 총 $N$가지 색깔의 꽃이 존재하니 전체 상처의 개수는 $N\cdot \frac{s(s - 1)}{2}$이다

- 이것이 $K$를 넘으면 안 되므로 $N\cdot \frac{s(s - 1)}{2} \le K$이고 정리하면 $s^2 - s \le \frac{2K}{N}$이다

- $(s - 1)^2 \le s^2 - s \le \frac{2K}{N}$이므로 $s\le \sqrt\frac{2K}{N} + 1$이고 이를 만족하는 $s$ 중 최댓값은 $\left\lfloor\frac{\left\lfloor\sqrt{2NK}\right\rfloor}{N}\right\rfloor + 1$이다 ($s$가 자연수이므로 소수점 이하는 필요 없음에 유의하자). 단, 이렇게 계산된 $s$는 $(s-1)^2$을 최대로 만들 때의 $s$이니 실제로는 이보다 더 작아져야 할 수 있다. 전체 상처 개수가 $K$를 넘지 않을 때까지 $s$를 $1$씩 감소시키자. 초깃값을 잘 정했으므로 최적의 $s$를 구하기 위해 필요한 반복 횟수는 그리 많지 않다

- 여기서 장미를 최대 $N-1$개 더 늘릴 수 있다. 장미가 하나 추가될 때마다 상처는 $\frac{s(s + 1)}{2} - \frac{s(s - 1)}{2} = s$개 늘어난다. 상처 개수의 여유분은 $K - N\cdot \frac{s(s - 1)}{2}$이며 이것이 $s$ 이상일 동안 장미를 추가할 수 있다

- 최종적으로 계산된 장미 개수를 출력하자. 단, $M$을 초과하는 경우 $M$을 출력하면 된다

import math


def solve_testcase(n, m, k):
    s = 1 + math.isqrt(2 * n * k) // n
    while n * s * (s - 1) > 2 * k:
        s -= 1
    n_flowers = n * s
    n_scratches = n * (s * (s - 1)) // 2
    rest = k - n_scratches
    for _ in range(n):
        if rest < s:
            break
        n_flowers += 1
        rest -= s
    return min(n_flowers, m)


def solution():
    Q = int(input())
    for _ in range(Q):
        N, M, K = map(int, input().split())
        answer = solve_testcase(N, M, K)
        print(answer)


solution()