2025년도 정보올림피아드 2차대회
2025년 KOI 2차대회
2025년도 한국정보올림피아드 2차대회 문제풀이 입니다.
갈수록 제 머리가 나빠지는 것인지 아니면 대회 문제가 점점 어려워지는 것인지, 쉽지 않습니다.
제 주관적인 관점에서 볼 때, 대회 초, 중등부 난이도는 대학 전공자 3학년 이상 수준이며, 고등부는 기업입사 면접문제보다 어렵다고 생각합니다.
그래도 해야지 답이 없습니다. 😅
 |
| [해인사에서 만난 무서운 비석] |
시간나는대로 풀고 업데이트하겠으며, 오답, 만점이 아닌 경우도 존재합니다.
초등부 장애물
첫 문제라 쉽습니다. 장애물 개수만큼 반복하며 장애물위치-내위치를 비교해 가며 이동하면 풀 수 있습니다.
N = int(input())
X = list(map(int, input().split(' ')))
s = 0
e = X[-1]+1
i = 0
cnt = 0
while i<N:
if X[i] > s:
if X[i]-s==1:
s+=2
i+=1
elif X[i]-s==2:
s+=1
elif X[i]-s>2:
s = s+2
cnt += 1
else:
cnt = -1
break
print(cnt)
초등부 거울
저는 첫문제보다 어려웠는데 정답률은 더 높네요.
거울의 위치는 정렬되어 있으며 a, b의 값이 작은수, 큰수 or 큰수, 작은수 중 어떻게 적용되어야 커지는지 확인이 필요합니다.
N, a = map(int, input().split(' '))
b = list(map(int, input().split(' ')))
k = a
mid = N//2
na = N%2
if na==0:
# 짝수의 경우 반씩 나눠 좌, 우시작점에서 인덱스 증가
for i in range(mid):
k = 2*b[i]-k
k = 2*b[i+mid]-k
else:
# 홀수의 경우 반대 순서, 마지막 중간값처리
for i in range(mid):
k = 2*b[N-i-1]-k
k = 2*b[i]-k
k = 2*b[mid]-k
print(k)
초등부 통행료
처음에는 다익스트라와 헷깔렸습니다. 플로이드 워셜 알고리즘을 공부해보세요.
import sys
INF = float('inf')
# 입력처리
N,M = map(int, sys.stdin.readline().split(' '))
W = []
for i in range(M):
u, v = map(int, sys.stdin.readline().split(' '))
W.append((u-1,v-1))
dist = [[INF] * N for _ in range(N)]
for i in range(N):
dist[i][i] = 0
# 처음부터 연결도로 비용 1로 설정
for u,v in W:
dist[u][v] = 1
dist[v][u] = 1
# 전체 플로이드 워셜(모든 도로 비용 1기준)
for k in range(N):
for i in range(N):
for j in range(N):
# i, j 경로에 대해 i -> k -> j, 즉 k를 거치는게 더 짧은지 확인
dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
last_total = 0
for i in range(N):
for j in range(N):
last_total += dist[i][j]
#print(last_total, end='\n')
# 역으로 도로비용을 0으로 하나씩 변경
rdist = [0] * M
rdist[M-1] = last_total
for day in range(M-1, 0, -1):
u, v = W[day]
# 새로 0원이된 도로적용
for i in range(N):
for j in range(N):
new_dist = min(dist[i][u] + dist[v][j] , dist[i][v] + dist[u][j])
dist[i][j] = min (dist[i][j], new_dist)
# 총합 계산
total = 0
for i in range(N):
for j in range(N):
total += dist[i][j]
rdist[day-1] = total
for r in rdist:
#print(r, end='\n')
sys.stdout.write(f'{r}\n')
초등부 상자보관
큰상자안에 작은상자를 넣어 상자그룹을 생성한 후, 최대상자크기, 용량 그리고 최소상자 크기, 용량을 저장하는 방식으로 하다 마지막 예시에서 실패하였습니다.
생각해보니 단순 크기 비교만 할 것이 아니라 효율적인 상자배치가 요구되므로 순열을 통한 전체탐색으로 시도중입니다.
from itertools import permutations
N = int(input())
boxes = []
for i in range(N):
s, c = map(int, input().split(' '))
boxes.append((s,c))
def isInBox(a, b):
sa, ca = a
sb, cb = b
return sb <= ca
for i in range(1, N+1):
subbox = boxes[:i]
n = len(subbox)
# 최대 모든 박스가 개별그룹
cnt = n
# 상자 간 포함 관계를 전체 탐색 (모든 순열)
for p in permutations(range(n)):
# 다른상자에 들어갔는지
isin = [False] * n
for j in range(n):
for k in range(j + 1, n):
outer = subbox[p[j]]
inner = subbox[p[k]]
if not isin[p[k]] and isInBox(outer, inner):
isin[p[k]] = True
break
subcnt = isin.count(False)
cnt = min(cnt, subcnt)
print(cnt)
중등부 가방
물건의 무게가 입력시 정렬되어 있는줄 착오가 있었습니다. 무게별로 정렬하고, 미리 물건 누적합을 구해둡니다. 정렬되어 있다면, 주인이 가져간 물건 다음 물건부터 도둑이 가져갈 물건입니다.
#N:상점물건수, K:도둑훔겨갈갯수 C:주인가방최대무게
import sys
N, K, C = map(int, input().split(' '))
A = list(map(int, input().split(' ')))
A.sort()
# 누적합
pre = [0] * (N + 1)
for i in range(1, N + 1):
pre[i] = pre[i - 1] + A[i - 1]
for i in range(1, C + 1):
D = 0
for j in range(N + 1):
# 주인이 가져간 무게합
W = pre[j]
if W > i:
break
# 도둑에게 남은 물건
R = N - j
S = min(R, K)
P = 0
if S > 0:
# 남은 물건: A[j]부터 시작
# 도둑이 훔치는 물건: A[j]부터 Aj + S - 1]까지
P = pre[j+S] - pre[j]
# 4. 최대 피해 갱신
D = max(D, P)
sys.stdout.write(f'{D}\n')
중등부 로봇
점프대 위치를 집합으로 저장해 이진탐색을 활용, 점프 파워는 딕셔너리로 저장해 시도중입니다.
import sys
n = int(sys.stdin.readline())
jpos = set()
jpow = dict()
for i in range(n):
# x:점프대위치, p:초기점프파워, 점프후 2배증가
x, p = map(int, sys.stdin.readline().split(' '))
jpos.add(x)
jpow[x] = p
q = int(sys.stdin.readline())
for i in range(q):
# s에서 출발, t시간이 지난후 도달위치
s, t = map(int, sys.stdin.readline().split(' '))
jpow_copy = dict(jpow)
while t>0:
if s in jpos:
bs = s
s = s+jpow_copy[s]
jpow_copy[bs] = jpow_copy[bs]*2
else:
s-=1
t-=1
#print(s)
sys.stdout.write(f'{s}\n')
고등부 문제도 시간나는 대로 업데이트 하겠습니다.
감사합니다.
댓글
댓글 쓰기