한국정보올림피아드 문제풀이
안녕하세요.
올해도 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))
블록 쌓기
문제 백준링크
풀이
어렵다.😥
처음엔 단조수열 B전체를 입력수열의 평균값으로 설정하고, 나머지를 수열의 뒤에서부터 증가시키는 방식으로 시도 (실패 X)
방향을 살짝 전환해 단조증가가 깨지는 부분을 찾아 처음부터 깨진 부분까지 평균을 구해 채우고 나머지는 깨진부분의 뒤에서 채워가는 방식으로 시도 (18점)
아직 뭔가 놓친 부분이 있다.
대부분 만족하나 아래 입력의 경우 실패
50 0 3 1 0 3 1 1 3 2 1 1 0 0 0 4 0 0 1 0 2 1 2 0 0 1 0 0 0 2 1 1 0 1 0 2 2 0 1 3 2 0 0 1 0 2 1 1 1 0 2 1 2 # 정답 81, 84출력
# 풀이과정 (최소횟수로 단조증가)
# 1. 원래 수열 X : 2 0 9 1 4
# 2. 단조 수열 B : B1...BN 단 (∑A 는 ∑B와 같다)
# 3. 최소 수열합 : N*L
# 4. 최대 수열합 : N*R
# 5. 가능 수열합(S) : S<N*L 또는 S>n*R 이면 불가능
# 6. 최소 수열합 : 답은 누적합 불일치의 합 (블록이 이동할 때마다 좌,우가 변경조정되기 때문)
def find_sequence(N, L, R, S):
B = list(A)
i = 0
while i<N-1:
if B[i] > B[i+1]:
avg = sum(B[0:i+2]) // (i+2)
k = sum(B[0:i+2]) % (i+2)
for j in range(i+2):
B[j] = avg
if k>0:
for j in range(i+1, -1, -1):
B[j] += 1
k-=1
if k<=0:
break
i+=1
elif B[i+1]>R:
avg = sum(B[0:i+2]) // (i+2)
k = sum(B[0:i+2]) % (i+2)
for j in range(i+2):
B[j] = avg
if k>0:
for j in range(i+1, -1, -1):
B[j] += 1
k-=1
if k<=0:
break
#print(i, B)
i+=1
else:
i+=1
return B
N, L, R = map(int, input().split())
A = list(map(int, input().split()))
# 수열합
S = sum(A)
minS = N*L
maxS = N*R
#print(S)
if S>=minS and S<=maxS:
B = find_sequence(N, L, R, S)
#print(B)
# A누적합 : 2 0 9 1 4 -> 2 2 11 12 16
# B누적합 : 3 3 3 3 4 -> 3 6 9 12 16
# B-A : 1 4 2 0 0 = 7
sumA = 0
sumB = 0
cnt = 0
for i in range(N):
sumA += A[i]
sumB += B[i]
cnt += abs(sumB-sumA)
#print(sumA)
#print(sumB)
print(cnt)
else:
print(-1)
KOI 2022 2차대회
제자리
문제 백준링크
풀이
n = int(input())
a = list(map(int, input().split()))
k = 0
cnt = 0
for i in range(n):
if a[i] == k+1:
k+=1
else:
cnt+=1
print(cnt)
KOI 2022 1차대회
빵
문제 백준링크
풀이
import heapq
import sys
n = int(input())
hq = []
for i in range(n):
a, b = map(int, sys.stdin.readline().rstrip().split(' '))
if b>=a:
heapq.heappush(hq, b)
if not hq:
print(-1)
else:
print(heapq.heappop(hq))
KOI 2021 2차대회
사각형 면적
문제 백준링크
풀이
import sys
n, c = map(int, sys.stdin.readline().rstrip().split(' '))
row, col = n, n
xa = 0
ya = 0
for i in range(c):
y, x = map(int, sys.stdin.readline().rstrip().split(' '))
xa = x*row
ya = y*col
#print(f'Size : {ya} / {xa}')
if ya==xa:
row -= (row-y)
elif ya>xa:
row -= (row-y)
else:
col -= (col-x)
print( xa if xa>ya else ya )
시간 날 때마다 문제, 해설을 추가할 계획입니다.
감사합니다.
댓글
댓글 쓰기