[백준]230320-26 문제풀이

23843. 콘센트

import heapq
import sys
input = sys.stdin.readline

N, M = map(int, input().split())
lst = list(map(int, input().split()))
lst.sort()
q = []
temp = []
ans = 0
while lst:
    now = lst.pop()
    heapq.heappush(q, now)
    if len(q) == M:
        out = heapq.heappop(q)
        ans += out
        for i in range(M - 1):
            q[i] -= out
        while q and q[0] == 0:
            heapq.heappop(q)
if q:
    ans += max(q)

print(ans)

힙을 콘센트로 두고 전자기기를 하나씩 넣어주면서 콘센트가 꽉 찼을 때 빠지는 기기(남은 충전시간이 제일 작은 기기)의 충전시간만큼 답에 더해줬다. 그리고 그 충전시간만큼을 전체 힙에서 빼주고 0이 되는 것들을 빼줬다. 힙 사용이 능숙하다면 금방 풀 수 있는 문제

20040. 사이클 문제

import sys
input = sys.stdin.readline

n, m = map(int, input().split())
ans = 0
parent = [_ for _ in range(n)]

def find(x):
    if x == parent[x]:
        return x
    else:
        parent[x] = find(parent[x])
        return parent[x]

def union(x, y):
    global ans
    x = find(x)
    y = find(y)
    if x != y:
        parent[max(x, y)] = min(x, y)
    elif not ans:
        ans = i + 1

for i in range(m):
    a, b = map(int, input().split())
    union(a, b)

print(ans)

처음으로 풀어본 유니온 파인드 문제. 첨에 혼자 못풀겠어서 구글링을 좀 했는데, x와 y의 조상을 각각 찾아갈 때 parent 배열을 이용하는 것이 포인트인데, 이번에는 보고 풀었으니 다음에 다른 문제를 혼자 풀어봐야겠다

18870. 좌표 압축

import sys
input = sys.stdin.readline

N = int(input())
lst = list(map(int, input().split()))
lst2 = sorted(list(set(lst)))
dic = dict()
for i in range(len(lst2)):
    dic[lst2[i]] = i
for i in lst:
    print(dic[i], end=' ')

이것도 도저히 못풀겠어서 찾아봤는데 딕셔너리도 set처럼 요소 찾을 때 시간복잡도가 O(1)이라 이런 문제에서 잘 활용할 수 있을 것 같다. 티어가 낮아서 그런지 이런 기초적인 지식이 부족하면 잘 못 풀게 되는 것 같다.

9290. 틱택토 이기기

import sys
input = sys.stdin.readline

dy = [-1, -1, -1, 0, 0, 1, 1, 1]
dx = [-1, 0, 1, -1, 1, -1, 0, 1]

def tictactoe(y, x, ox):
    for d in range(8):
        if y + dy[d] not in range(3) or x + dx[d] not in range(3):
            continue
        if lst[y + dy[d]][x + dx[d]] == ox:
            if y + dy[d]*2 in range(3) and x + dx[d]*2 in range(3):
                lst[y + dy[d]*2][x + dx[d]*2] = ox
            else:
                lst[y - dy[d]][x - dx[d]] = ox
            return
        if y + dy[d]*2 not in range(3) or x + dx[d]*2 not in range(3):
            continue
        if lst[y + dy[d]*2][x + dx[d]*2] == ox:
            lst[y + dy[d]][x + dx[d]] = ox


T = int(input())
for tc in range(1, T + 1):
    lst = [list(input().strip()) for _ in range(3)]
    ox = input().strip()
    for r in range(3):
        for c in range(3):
            if lst[r][c] == ox:
                tictactoe(r, c, ox)
    print(f'Case {tc}:')
    for _ in range(3):
        print(*lst[_], sep='')

내가 사랑하는 브루트포싱과 구현... 테케 맞춰볼 수 있는 코테면 몰라도 아니라면 출력 형식에 주의를 좀 기울여야 할 것 같다. Case n: 이 부분을 쉽게 틀리게 되는듯...

20208. 진우의 민트초코 우유

import sys
input = sys.stdin.readline

def dfs(n, hp, visited):
    global ans
    if len(visited) > ans and hp >= dist[n][n]:
        ans = len(visited)
    for nxt in range(len(mcm)):
        if nxt in visited:
            continue
        if dist[n][nxt] > hp:
            continue
        dfs(nxt, hp - dist[n][nxt] + H, visited + [nxt])

N, M, H, = map(int, input().split())
lst = [list(map(int, input().split())) for _ in range(N)]
mcm = []
for i in range(N):
    for j in range(N):
        if lst[i][j] == 2:
            mcm.append((i, j))
        if lst[i][j] == 1:
            home = (i, j)
dist = [[0] * 10 for _ in range(10)]
for i in range(len(mcm)):
    for j in range(len(mcm)):
        if i == j:
            dist[i][i] = abs(mcm[i][0] - home[0]) + abs(mcm[i][1] - home[1])
        else:
            dist[i][j] = dist[j][i] = abs(mcm[i][0] - mcm[j][0]) + abs(mcm[i][1] - mcm[j][1])

ans = 0
for i in range(len(mcm)):
    if dist[i][i] > M:
        continue
    dfs(i, M - dist[i][i] + H, [i])

print(ans)

이렇게 더럽게 푸는게 맞는진 모르겠지만... 어쨌든 맞았으니 오케이. 체력을 계속 모니터링 해주면서 dfs를 돌려보고 먹은 우유의 개수가 최대가 될 때 집으로 돌아갈 수 있는지의 여부를 dist 배열에서 dist[i][i]로 확인할 수 있도록 했다. 아이디어가 나름 괜찮은 것 같아서 뿌듯

25168. 게으른 아리를 위한 접종 계획

import sys
input = sys.stdin.readline

N, M = map(int, input().split())
ans = [0] * (N + 1)
for _ in range(M):
    S, E, W = map(int, input().split())
    if not ans[S]:
        ans[S] = 1
    if W >= 7:
        W += 1
    ans[E] = max([ans[S] + W, ans[E]])
print(max(ans))

문제만 이해하면 DP 풀듯 풀면 되는데, 멍청하게 마지막 N번째의 백신을 제일 마지막에 맞는걸로 생각해서 계속 로직만 들여다보고 있었다. ans[N]이 아닌 max(ans)를 해주는게 포인트

1806. 부분합

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

N, S = map(int, input().split())
arr = list(map(int, input().split()))
q = deque()
ans = 1e10

qsum = 0
while arr:
    now = arr.pop()
    qsum += now
    q.append(now)
    if qsum >= S:
        while qsum - q[0] >= S:
            qsum -= q.popleft()
        if len(q) < ans:
            ans = len(q)
        qsum -= q.popleft()
if ans == 1e10:
    ans = 0
print(ans)

deque를 사용하면서 배열의 값들을 하나씩 넣어주고, 합이 S가 넘었을 때 선입선출 해주면서 최소한의 길이를 유지하도록 해준다. 답을 갱신하고 나면 또 맨 앞의 요소를 하나 빼주고 똑같은 과정을 반복하면서 답을 갱신해준다.

1783. 병든 나이트

import sys
input = sys.stdin.readline

N, M = map(int, input().split())
if N == 1:
    print(1)
elif N == 2:
    print(min(4, (M + 1) // 2))
elif M < 7:
    print(min(4, M))
else:
    print(M - 2)

코테에서 가장 중요한 것 중 하나가 어떤 알고리즘을 써야할지 깨닫는건데, 난 이걸 dfs로 풀어보려고 계속 삽질했다... 다음에 로직이 분명 맞는데도 시간이나 메모리가 부족하다면 dp나 그리디로 눈을 돌려서 생각해보는 유연함이 필요할 것 같다.