백준 오픈 콘테스트 참여하기
첫 번째
- 언젠가 대회에 제대로 참여해보고 싶었는데 할만한(?) 실력도 됐고 시간도 마침 괜찮아서 참여했다
- 참여한 대회는 2026 IamCoder Qualification Test Open이다
- 제한 시간은 3시간에 A번부터 I번까지 총 9문제로 A,B,C,D번 풀어서 총 4솔 했다
- 평상시에 골랜디 안 했으면 아마 2문제 풀고 끝났을 것이다
- 맞힌 문제에 대해선 어떻게 풀었는지 알아보자 (단, 코드는 대회에 제출했던 건 아니고 리팩토링 한 것이다)
- 풀지 못한 문제는 언젠가 업솔빙하면 좋겠다
A번 - 문자열 회전
- 문제 출처: 백준 35429번
- $r = l+1$인 경우를 고려해보자
- 이는 두 문자의 위치를 바꾸는 것이 된다
- 이를 반복하면 임의의 문자를 내가 원하는 위치에 집어 넣을 수 있다
- 따라서 부분 문자열 GSHS의 개수는 문자열 $S$에 존재하는 G, S, H의 개수에만 영향을 받는다
- $6$분 걸렸고 $1$번에 맞혔다
from collections import Counter
def solution():
N = int(input())
S = input()
s = Counter(S)
answer = min(s["G"], s["S"] // 2, s["H"])
print(answer)
solution()
# input
# 10
# GSHSHSGSHH
- 예상 티어: 실버 $5$
B번 - 직사각형 색칠하기
- 문제 출처: 백준 35430번
- 생각보다 까다로운 문제였다
- $X=ab$이고 $a\le N, b \le M$이라면 $K=1$이다
- 이때 $x_1,y_1,x_2,y_2 = 0, 0, a, b$이다
- 그렇지 않다면 $X=qN+r,(0\le r < N)$이라 할 때 넓이가 $qN$인 직사각형과 넓이가 $r$인 직사각형으로 나눌 수 있다
- 첫 번째 직사각형의 경우 $x_1,y_1,x_2,y_2 = 0, 0, N, q$이며 두 번째 직사각형의 경우 $x_1,y_1,x_2,y_2 = 0, q, r, q+1$이다
- $r < N$이며 $q=M$인 경우 $X=NM$으로 애초에 $K=1$이다 ($X \le NM$ 조건 유의)
- 따라서 $q < M$이고 이에 따라 $q+1 \le M$이므로 $0\le x_1<x_2\le N, 0\le y_1<y_2\le M$을 만족한다
- $K=1$이 가능한지 확인하기 위해 $X=ab$를 만족하는 모든 $a,b$에 대해 $a\le N, b \le M$인지 확인하자
- 이는 $O(\sqrt{NM})$이다
- $K=1$이 불가능하다면 자연스레 $K=2$이다
- 따라서 전체 알고리즘의 시간 복잡도는 $O(\sqrt{NM})$이며 $N,M\le 10^5$이므로 제한 시간 안에 동작한다
- $53$분 걸렸고 $4$번 만에 맞혔다
- 처음에 인수분해 코드에서 $i$의 범위를 $\operatorname{range}(1,n)$으로 코딩해서 계속 틀렸었음
def check_k1(n, m, x):
factors = factorize(x)
for a, b in factors.items():
if a <= n and b <= m:
print(1)
print(0, 0, a, b)
return True
return False
def factorize(n):
factors = {}
for i in range(1, n + 1):
if i * i > n:
break
if n % i != 0:
continue
factors[i] = n // i
factors.update({b: a for a, b in factors.items()})
return factors
def run_k2(n, m, x):
q = x // n
r = x % n
print(2)
print(0, 0, n, q)
print(0, q, r, q + 1)
def solution():
N, M, X = map(int, input().split())
if check_k1(N, M, X):
return
run_k2(N, M, X)
solution()
# input
# 8 6 32
- 예상 티어: 실버 $2$
C번 - Connect the GSHS 2
- 문제 출처: 백준 35431번
- 수도에서 가장 먼 마을까지의 거리를 최소화해야 한다
- 도시 중 한 곳이 수도이다
- 정의상 수도에서 어떤 마을까지 가는 경로엔 해당 마을의 도시가 포함되어야 한다
- 따라서 수도에서 가장 먼 마을까지의 거리를 최소화하려면 왕국 내 도시에서 가장 먼 왕국 내 마을까지의 거리를 최소화해야 한다
- 이는 왕국 내 모든 마을에 대해 한 번씩 번갈아가며 도시로 가정한 뒤 BFS를 수행해 실현할 수 있다
- 이를 모든 왕국에 대해 수행하는 건 최악의 경우 $O\left(KN^2 M\right)$이다 ($N=\max(N_i), M=\max(M_i)$)
- 이제 왕국마다 도시를 정했으니 $K$개의 도시를 선형으로 이은 뒤 이 중 한 곳을 수도로 정하면 된다
- 이때 간선의 개수는 $K-1$개로 정점의 개수보다 $1$개 부족하므로 도시끼리 연결된 그래프는 트리가 된다
- 수도를 트리 상에서 루트 노드라고 가정해보자
- 각 도시는 최대 $2$개의 다른 도시와 연결될 수 있다
- 따라서 수도를 제외한 다른 도시는 최대 $1$개의 자식 노드만 가질 수 있다 (나머지 $1$개는 부모 노드)
- 임의의 도시가 트리 상에서 노드 $u$ 일 때 노드 $u$의 가중치 $w_u$를 왕국 내 도시($u$)에서 가장 먼 왕국 내 마을까지의 거리라고 하자
- 그럼 수도와 도시가 노드 $u$인 마을 사이의 거리의 최댓값은 $\operatorname{depth}_u + w_u$이다 ($\operatorname{depth}_u$는 트리 상에서 노드 $u$의 깊이)
- 트리 상에서 노드 $v$인 수도와 노드 $u$인 도시에 대해 트리에서 둘의 위치를 서로 바꾸면 결과는 $\operatorname{depth}_v + w_v$가 된다
- 이때 $\operatorname{depth}_u =\operatorname{depth}_v$이므로 $w_u$와 $w_r$만 비교하면 된다
- 교환 논증에 따라 결과적으로 노드의 가중치가 가장 큰 도시를 수도로 정해야 한다
- 그럼 이제 트리 상에서 깊이가 $0$인 루트 노드는 선택했으니 깊이가 $1$인 두 노드를 골라야 한다
- 이는 깊이만 $0$에서 $1$로 바뀌었을 뿐 나머지는 동일하다
- 따라서 교환 논증에 따라 노드의 가중치가 큰 도시부터 선택해 현재 트리 상에서 깊이가 가장 작은 노드로 명하면 된다 (트리는 빈 집합부터 시작)
- 가중치를 기준으로 도시를 정렬해야 하니 시간 복잡도는 $O(N\log N)$이 된다
- 트리가 완성되고 수도에서 가장 먼 마을까지의 거리를 계산하는 건 $O(N)$이다
- 전체 알고리즘의 시간 복잡도는 $O\left(KN^2 M + N\log N\right)$이다
- $30$분 걸렸고 $1$번에 맞혔다
from collections import deque
def minimize_distance_from_capital(graphs):
min_weights = []
for graph in graphs:
w = compute_city_weight(graph)
min_weights.append(w)
min_weights.sort(reverse=True)
min_distance = min_weights[0]
depth = 1
for i, w in enumerate(min_weights[1:]):
min_distance = max(w + depth, min_distance)
if i % 2 == 1:
depth += 1
return min_distance
def compute_city_weight(graph):
n = len(graph)
min_weight = INF
for city in range(1, n):
weight = bfs(graph, city)
if weight < min_weight:
min_weight = weight
return min_weight
def bfs(graph, start):
n = len(graph)
queue = deque([start])
distances = [NONE] * (n + 1)
distances[start] = 0
while queue:
u = queue.popleft()
for v in graph[u]:
if distances[v] != NONE:
continue
distances[v] = distances[u] + 1
queue.append(v)
return max(distances)
def solution():
global INF, NONE
INF = float("inf")
NONE = -1
K = int(input())
graphs = []
for _ in range(K):
N, M = map(int, input().split())
graph = [[] for _ in range(N + 1)]
for _ in range(M):
s, e = map(int, input().split())
graph[s].append(e)
graph[e].append(s)
graphs.append(graph)
answer = minimize_distance_from_capital(graphs)
print(answer)
solution()
# input
# 3
# 3 3
# 1 2
# 2 3
# 3 1
# 4 4
# 1 2
# 2 3
# 3 4
# 4 1
# 2 1
# 1 2
- 예상 티어: 골드 $4$
- 내용 정리하고 보니까 티어 조금 낮게 매긴 듯
D번 - 눈부신 조명
- 문제 출처: 백준 35432번
- 처음엔 소신발언 문제와 비슷한 부류라고 생각해 이분 탐색으로 접근했었다
- 삽질 좀 하다가 제대로 된 풀이가 떠올랐다
- 모든 $l_i$는 다르다
- $m$번째 조명의 등급이 가장 크다고 하자
- 그럼 위치 $p_m$은 해당 조명에 의해 밝기가 $A^{l_m}$만큼 증가한다
- 최대 등급의 조명을 제외한 나머지 조명이 모두 같은 위치에 있다고 할 때 해당 위치의 밝기를 계산하면 다음과 같다
- $A^{l_1} + \cdots + A^{l_N}$ (단, $A^{l_m}$은 제외, 멀리 떨어져 있다고 생각하자)
- 이때 $A^{l_m} > A^{l_1} + \cdots + A^{l_N}$이 성립한다 (증명은 생략, 수학적 귀납법으로 가능)
- 따라서 지하철 선로에서 최대 밝기가 나타나는 위치는 $l_m$ 등급의 조명에 의해 밝기가 증가하는 위치 중 하나이다
- $L_{i,x}$ 계산 공식에 의해 최대 밝기가 나타나는 위치를 $x$라 할 때 $p_{m} - d_m < x < p_{m} + d_m$이 성립한다
- 최대 $2d-2$개의 위치를 순회하며 해당 위치의 밝기를 계산하면 된다
- 근데 단순하게 밝기를 계산할 수는 없다 (수가 너무 커짐)
- 그렇다고 나머지 연산을 적용하면 대소 관계가 틀어질 수 있다
- $A^{l_m} > A^{l_1} + \cdots + A^{l_N}$ 식과 같은 특성을 사용하여 비교하자
- 가능한 모든 $x$별로 $L_{i,x} \le 0$를 만족하는 모든 $L_{i,x}$를 내림차순 정렬해서 가지고 있자
- 이를 기준으로 밝기를 비교하면 된다
- 그 후 최대 밝기가 나타나는 위치의 실제 밝기를 계산하면 된다
- $A^{l_i}$를 $10^9+7$로 나눈 나머지는 분할 정복을 통해 $O(l_i)$에 계산할 수 있다
- 전체 알고리즘의 시간 복잡도는 최악의 경우 $O(dN\log N + \log l)$이다
- $d$는 최대 $100$이고 $l$은 최대 $10^9$이며 $N$은 최대 $10000$이므로 제한 시간 안에 동작할 수 있다
- $71$분 걸렸고 $1$번에 맞혔다
def measure_light(x, lamps):
light = []
for p, l, d in lamps:
L_ix = compute_L_ix(x, p, l, d)
if L_ix < 0:
continue
light.append(L_ix)
light.sort(reverse=True)
return light
def compute_L_ix(x, p, l, d):
L_ix = l - (abs(p - x) // d)
return L_ix
def solution():
mod = 10**9 + 7
N, A = map(int, input().split())
lamps = [list(map(int, input().split())) for _ in range(N)]
lamps.sort(key=lambda lamp: lamp[1])
p, l, d = lamps[-1]
lights_info = []
for x in range(max(p - d + 1, -10**9), min(p + d, 10**9 + 1)):
light = measure_light(x, lamps)
lights_info.append((light, x))
lights_info.sort()
light, x = lights_info[-1]
max_brightness = 0
for L_ix in light:
max_brightness += pow(A, L_ix, mod)
max_brightness %= mod
print(max_brightness)
print(x)
solution()
# input
# 3 4
# 2 3 2
# 3 1 2
# 4 2 1
- 예상 티어: 골드 $1$