한국정보올림피아드 문제풀이
안녕하세요.
올해도 KOI 대회를 준비하는 학생들이 있어 문제풀이를 시간날 때 마다 포스팅하려 합니다.
풀이 결과가 100점이 아닌 경우도 있습니다.
여러분도 도전해보세요~😉
KOI 2024 2차대회
보물찾기
문제 백준링크
풀이
반복문으로 풀면 시간초과.
왼쪽, 오른쪽, 현재위치를 이용하면 규칙성이 보임.
t = int(input())
for _ in range(t):
l, r, s = map(int, input().split(' '))
lr = set([l, r])
if s in lr:
print(1)
else:
a = s-l
b = r-s
if a<b:
print(a*2+1)
elif a>b:
print(b*2)
else:
print(a*2)
가로등
문제 백준링크
풀이
위치와 어두운 정도를 묶어서 딕셔너리로 정리.
이후 어두운 정도를 기준으로 정렬 후 출력.
from collections import deque
import sys
L, N, K = map(int, sys.stdin.readline().rstrip().split(' '))
lst = list(map(int, sys.stdin.readline().rstrip().split(' ')))
visit = set()
q = deque()
d = dict()
for i in range(N):
visit.add(lst[i])
d[lst[i]] = 0
q.append(lst[i])
cnt = 0
while q:
i = q.popleft()
cnt += 1
if i - 1 >= 0 and i - 1 not in visit:
d[i - 1] = d[i] + 1
visit.add(i - 1)
q.append(i - 1)
if i + 1 <= L and i + 1 not in visit:
d[i + 1] = d[i] + 1
visit.add(i + 1)
q.append(i + 1)
if cnt >= K:
break
# value 기준 정렬
#print(d)
sd = sorted(d.items(), key=lambda x:x[1])
#print(sd)
for i in range (K) :
print(sd[i][1])
색깔모으기
문제 백준링크
풀이
이걸 초딩이 푼다고? 대단...미리 싸인받아놓고 싶다.
무향그래프의 사이클과 유향그래프의 진출차수를 활용.
from collections import defaultdict
import sys
N = int(sys.stdin.readline().rstrip())
A = []
B = []
for i in range(N):
a, b = list(map(int, sys.stdin.readline().rstrip().split(' ')))
A.append(a)
B.append(b)
# deg:진출차수, g:무방향그래프
deg = defaultdict(int)
g = defaultdict(list)
colors = set()
for i in range(N):
a = A[i]
b = B[i]
deg[a] += 1
if a==b:
continue
# if a != b:
# deg[b] += 0
g[a].append(b)
g[b].append(a)
colors.add(a)
colors.add(b)
# print(deg)
# print(g)
# print(colors)
visited = set()
result = 0
def dfs(u, cycle_nodes):
visited.add(u)
cycle_nodes.append(u)
for v in g[u]:
if v not in visited:
dfs(v, cycle_nodes)
for color in colors:
if color not in visited:
cycle_nodes = []
dfs(color, cycle_nodes)
#print(cycle_nodes)
if len(cycle_nodes) == 1:
print(0)
#continue
exit()
outdeg_count = sum(1 for c in cycle_nodes if deg[c] >= 2)
#print(outdeg_count)
if outdeg_count >= 2:
print(-1)
exit()
result += len(cycle_nodes) + 1 # 사이클 크기 + 1
print(result)
KOI 2024 1차대회
등교
문제 백준링크
풀이
쉬운문제 s + t가 x보다 작은 것 중 가장 큰것.
n, x = map(int, input().split(' '))
lst = []
for i in range(n):
s, t = map(int, input().split(' '))
if s+t > x:
lst.append(-1)
else:
lst.append(s)
print(max(lst))
두배
문제 백준링크
풀이
반복문을 이용하면 시간초과.
Math Library Log(), ceil()을 사용해 틀림.
내장 로그함수를 사용해 틀린 후 다시 풀어본 문제.
n = int(input())
a = list(map(int, input().split(' ')))
log = [0] * (250000+1)
_max = 20 # 2^max = 1,000,000 이상
def mylog(x, y):
nx, ny = x, y
for i in range(_max):
nx *= 2
for i in range(-_max, 0):
if nx <= ny:
return i
nx /= 2
for i in range(_max):
if nx <= ny:
return i
ny *= 2
return _max
for i in range(1, n):
log[i] = mylog(a[i-1], a[i])
cnt = 0
for i in range(1, n):
if log[i] > 0:
cnt += log[i]
log[i+1] += log[i]
print(cnt)
반품회수
문제 백준링크
풀이
일단 맨 오른쪽 끝으로 이동한 후 왼쪽으로 이동하며 처리.
n = int(input())
x = list(map(int, input().split(' ')))
t = list(map(int, input().split(' ')))
tm = x[-1]
if tm < t[-1]:
tm = t[-1]
for i in range(n-2, -1, -1):
tm += x[i+1] - x[i]
if tm < t[i]:
tm += t[i] - tm
tm += x[0]
print(tm)
회의장소
문제 백준링크
풀이
import bisect
import sys
def count_in_range(lst, a, b):
left = bisect.bisect_left(lst, a)
right = bisect.bisect_right(lst, b)
return lst[left:right]
def get_tired(m):
# 집좌표 누적합, h[3]는 m[0] + m[1] + m[2].
h = [0]
for i in m:
h.append(h[-1] + i)
# h[i] = m[0] + m[1] + ... + m[i-1]
total = h[-1]
v = []
n = len(m)
for i in range(n):
# m[0] ~ m[i-1]까지의 합
left_sum = h[i]
# m[i] ~ m[n-1]까지의 합
right_sum = total - h[i+1]
cost = m[i] * i - left_sum + right_sum - m[i] * (n - i - 1)
v.append(cost)
return v
n, q = map(int, sys.stdin.readline().rstrip().split(' '))
x = list(map(int, sys.stdin.readline().rstrip().split(' ')))
for _ in range(q):
l, r = map(int, sys.stdin.readline().rstrip().split(' '))
m = count_in_range(x, l, r)
#print(m)
if len(m) <= 1:
print(0)
continue
v = get_tired(m)
max_v = max(v)
min_v = min(v)
#print(max_v-min_v)
sys.stdout.write(str(max_v-min_v) + '\n')
KOI 2023 2차대회
불안정한 수열
문제 백준링크
풀이
N = int(input())
B = list(map(int, input().split(' ')))
cnt = 0
for i in range(N-1):
if (B[i] + B[i+1])%2==1:
cnt+=1
print(cnt+1)
KOI 2023 1차대회
크림빵
문제 백준링크
풀이
n, k, p = map(int, input().split(' '))
lst = list(map(int, input().split(' ')))
s = 0
for i in range(n):
c = 0
for j in range(k):
h = (i*k)+j
if lst[h]==0:
c+=1
if c<p:
s+=1
print(s)
대피소
문제 백준링크
풀이
from itertools import combinations
def manhattan(a, b):
return abs(a[0] - b[0]) + abs(a[1] - b[1])
def is_valid(houses, candidates, K, r):
for shelters in combinations(candidates, K):
ok = True
for h in houses: # 각 집에 대해
covered = False # 이 집이 r 거리 내 대피소와 연결 가능한지 여부
for s in shelters: # 선택된 대피소들 중 하나와 비교
if manhattan(h, s) <= r: # 거리가 r 이하면
covered = True # 이 집은 커버 가능함
break # 더 볼 필요 없이 탈출
if not covered:
ok = False # 이 집은 어떤 대피소와도 연결 안 됨
break # 하나라도 실패했으니 이 조합은 안 됨
if ok:
return True # 하나라도 성공한 조합이 있다면 전체적으로 가능함
# 모든 조합을 다 시도했지만 안 됨
return False
def find_min_max_distance(houses, K):
left, right = 0, 200_000
answer = right
while left <= right:
mid = (left + right) // 2
if is_valid(houses, houses, K, mid):
answer = mid
right = mid - 1
else:
left = mid + 1
return answer
# 입력 처리
n, k = map(int, input().split())
houses = [tuple(map(int, input().split())) for _ in range(n)]
#print(houses)
# 결과 출력
print(find_min_max_distance(houses, k))
시간 날 때마다 문제, 해설을 추가할 계획입니다.
감사합니다.
댓글
댓글 쓰기