정올 1차 1, 2번 문제 풀이

 

 

최근에 1차 대회 문제 몇개를 풀었는데, 문제 퀄리티가 좋다고 생각해서 풀이를 정리해볼까 한다. 

 

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

25379번: 피하자

처음 봤을땐 구현을 어떻게 해야하나 막막했는데, 차분히 생각해보니 구현이 어려운 문제는 아니었다. 결국 홀수와 짝수를 한쪽으로 밀어야하는데, 홀수를 밀든 짝수를 밀든 결국 횟수는 같다. mod 2를 해주고 왼쪽으로 밀어보고, 오른쪽으로도 밀어본 다음 최솟값을 출력하면 된다. 

시간복잡도는 O(N)이다.

import sys
input = sys.stdin.readline

n = int(input())
a = list(map(int, input().split()))
ans = [0, 0]
li = 0
for i in range(n):
    a[i] %= 2
    if a[i]:
        ans[0] += i - li
        li += 1

ri = n-1
for i in range(n):
    if a[i]:
        ans[1] += ri - i
        ri -= 1

print(min(ans))

 

 

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

25381번: ABBC

이 문제는 도저히 풀이를 모르겠어서 답을 봤다. 풀이를 봐도 이게 왜 골드 4인지는 잘 모르겠다. 그리디는 티어의 기준을 알기 어렵다.

기본적인 관찰 : B - C를 먼저 사용하고 A - B를 사용하는게 이득이다.

가장 왼쪽에 있는 B와 또 가까이 있는 C를 먹고, 남는 B를  A로 먹어주면 된다. 큐를 사용하면 쉽게 구현할 수 있다.

시간복잡도는 O(|S|)이다.

import sys
from collections import deque
input = sys.stdin.readline

s = str(input().rstrip())
n = len(s)
ans = 0
aq = deque()
bq = deque()

for i in range(n):
    if s[i] == "A":
        aq.append(i)
    if s[i] == "B":
        bq.append(i)
    if s[i] == "C" and bq:
        ans += 1
        bq.popleft()

while aq:
    cur = aq.popleft()
    while bq and bq[0] < cur:
        bq.popleft()
    if bq:
        ans += 1
        bq.popleft()

print(ans)

 

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

21760번: 야구 시즌

식을 구하기 굉장히 귀찮은 문제였다. 

A = Bk 라고 하자.

하나의 행을 기준으로 보면 그냥 nC2이고, 한 행에 m명의 사람이 있으니 다른 지역 리그와의 경기는 nC2 * m^2번 일어난다.

같은 지역 리그와의 경기는 한 행에서 2명을 선택하는 mC2가 n번 일어나니 mC2 * n 이다. 이제 여기에 비용을 붙여 식을 쓰면, 

$$b{m}^2(\genfrac{}{}{0ex}{}{n}{2})+(\genfrac{}{}{0ex}{}{m}{2})bkn\le D$$ 이 된다. b를 제외한 모든 값을 알고 있으니, 나머지를 이항하고 math.floor 하면 된다.

각 문제당 O(1)에 풀 수 있다.

import sys
input = sys.stdin.readline

t = int(input())
for _ in range(t):
    n, m, k, d = map(int, input().split())
    c = (m * m * (n * (n - 1)) // 2 + (m * (m - 1)) // 2 * k * n)
    ans = c * (d // c)
    if ans < c or ans > d: print(-1)
    else: print(ans)

 

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

21761번: 초직사각형

나한테는 이게 아까 ABBC 보다 쉬웠다. 맨 처음에는 dp를 생각했는데, 식을 어떻게 세울지도 잘 모르겠고 n도 크고 dp를 구했다 해도 답을 출력하는게 어지러울 것 같았다. 조금 생각해보니 부분 최적 구조가 성립하는 것 같았다. 일단 같은 문자를 봤을 때, 값이 더 큰 카드를 먼저 쓰는게 무조건 이득이다. 그럼 각 문자에 대해 정렬을 하고, 각 상태마다 넓이가 가장 크게 바뀌는 카드를 선택해주면 답이 나온다.

시간복잡도는 O(n log n + k) 가 된다.

import sys
input = sys.stdin.readline

n, k = map(int, input().split())
a, b, c, d = map(int, input().split())
cur = {}
cur['A'] = a
cur['B'] = b
cur['C'] = c
cur['D'] = d
v = a * b * c * d
l = {}
l['A'] = []
l['B'] = []
l['C'] = []
l['D'] = []
for i in range(n):
    t, u = map(str, input().split(" "))
    l[t].append(int(u))

for key in l: l[key].sort()

for _ in range(k):
    ans = v
    for key in l:
        if len(l[key]) > 0: ans = max(ans, v + (v // cur[key]) * l[key][-1])
    for key in l:
        if len(l[key]) > 0:
            if v + (v // cur[key]) * l[key][-1] == ans:
                print(key + " " + str(l[key][-1]))
                cur[key] += l[key][-1]
                l[key].pop()
                break
    v = ans

구현을 좀 깔끔하게 하고 싶어서 딕셔너리를 사용했는데 지금 보니 그냥 0 1 2 3으로 했음 됬을 것 같다..

 

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

17612번: 쇼핑몰

오늘 일어나자마자 커피 마시면서 풀어서 구현을 좀 절었다. 심지어 문제도 한번 잘못 이해해서 구현을 2번 했다. 이 문제는 문제에서 주어진 것을 그대로 구현하면 된다. 최솟값을 뽑아야하기에 계산대는 우선순위 큐로 구현해주면 되고, 같은 시간대에 빠져나오는 애들은 배열에 모아 자리에 대해 오름차순 정렬해주면 된다. 여기서 문제가 계산대에 나가는 고객은 오름차순인데 들어오는 고객은 내림차순이기에, 나가는 친구들의 자리를 배열에 저장해주고, 거꾸로 돌려서 들어오는애들을 보내주면 된다. 설명이 좀 이상한 것 같아 예를 들자면, 

(남은시간, 번호)

이렇게 있을 때, 나가는건 계산대 번호가 큰 3번 친구부터 나가기 때문에, 12, 11, 10 순으로 나가지만, 다음에 들어오는 애들은 1, 2, 3순으로 들어온다. 

여기서 남은 시간이 5인 애들이 나간다면 남은시간이 7, 9인 애들은 2, 4로 바뀌어야하는데, 항상 값을 빼주면 최악의 경우에는 O(NK)가 걸릴 수 있다. 그렇기에 새로 들어오는 손님에 나가는 손님의 값을 더해주면 된다.

import sys
import heapq
from collections import deque
input = sys.stdin.readline

n, k = map(int, input().split())
a = deque()
for _ in range(n):
    id, w = map(int, input().split())
    a.append([w, id])
ans = 0
q = []
for i in range(min(n, k)):
    heapq.heappush(q, a.popleft() + [i])
turn = 1
tmp = 0
while q:
    out = 1
    curs = []
    curs.append(heapq.heappop(q))
    while q and curs and q[0][0] == curs[0][0]:
        curs.append(heapq.heappop(q))
        out += 1
    curs.sort(key=lambda x:x[2])

    order = []
    cnt = 0
    while curs:
        cur = curs.pop()
        ans += cur[1] * turn
        turn += 1
        order.append(cur[2])
        cnt += 1
        tmp = cur[0]
    for i in range(cnt-1, -1, -1):
        if a:
            t = a.popleft()
            t[0] += tmp
            heapq.heappush(q, t + [order[i]])
print(ans)

이 문제에는 엄청난 함정이 있는데, 조건에 k가 n보다 작다는 말이 없다.. 이 때문에 index error가 엄청 많이 떴다.