[2024 KAUPC] 대회 문제 풀이(코드)

대회 개최를 끝내고, 간단하게 문제를 다시 풀어보았다. 다 푼건 아니고 스코어보드를 계속 보면서 정답률이 낮은 문제, 많은 사람들이 못 푼 문제 등을 다시 한번 풀어보았다. 문제가 나중에 수정된 문제들이 많아서 그냥 처음 푼다는 마인드로 다시 풀었다.

 

A번 기후동행카드

https://www.codetree.ai/problems/climate-card/description

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

 

올해도 수고를 해주신 KOALA (전)회장님이 내신 문제다. 이 문제가 1번 문제기도 하고, 좀 나중에 만들어진 문제라 직접 풀어본건 처음이었다.

단순 if문을 세워서 풀면 되는 문제였다.

a,b,c=map(int,input().split())
c1=1300*a+1100*b+500*c
c2=62000+500*c
c3=65000
print(min(c1,c2,c3))

 

C번 한진이의 상품뽑기

https://www.codetree.ai/problems/pick-maximum-mystery-gifts/description

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

 

이번 대회 문제 중 최대 복병이었다 ㅋㅋㅋㅋㅋ... 나도 맨 처음 풀어볼 때 한번 틀렸던 기억이 있다. 아마 테스트케이스를 2개를 주지 않았더라면 정답률이 더 낮았을 문제이다. 스코어보드를 보면 이 뒤의 문제보다 푼 사람이 적고, 정답률은 아마 전체 문제중 꼴등이지 않을까 싶다. 대회 도중에도 해당 문제를 건너뛰고 푸는 사람들이 많았고, 이 문제를 풀었냐 못풀었냐로 순위가 갈리기도 했다.

 

n,m,k=map(int,input().split())
arr=list(map(int,input().split()))
ov=0
for i in range(n):
    if arr[i]<m-1:
        if k:
            if m-arr[i]-1<=k:
                k-=(m-arr[i]-1)
                arr[i]=m-1
            else:
                arr[i]+=k
                k=0
    else:
        ov=1
        arr[i]=m-1
if k or ov:
    print(sum(arr)+1)
else:
    print(sum(arr))

 

검수할때 풀었던 방식은 4줄~6줄 사이로 끝났던 것 같은데 이번에는 조금더 세분화해서 풀어보았다. 건실하게 배열에서 하나하나 채워가면서 풀었고, 이미 한대 맞아서 조건 잘 신경써서 풀었다. k가 남거나, k가 부족해도 초기에 m개 이상 존재하는 묶음이 존재하면 +1을 해주어야 했다. 이래저래 문제를 잘 읽고 신경써줘야 했던 문제이다.

 

D번 곱빼기

https://www.codetree.ai/problems/mul-minus/description

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

 

내가 낸 문제다. 학교에서 시스템 프로그래밍 수업을 수강하면서 배운 개념을 문제로 출제한 것이다. (실제로 중간인가 기말에 이렇게 바꾸는 문제가 나왔다!) 어떻게 숫자를 구성해야 했는지 파악했다면 그 뒤로는 다양한 방법으로 단순 구현해주면 되는 문제였다. 딱히 함정이라 할 만한 요소가 없어서 정답률이 꽤 높았던 것 같다.

 

n=int(input())
a=1
i=0
ans=[]
while a<n:
    i+=1
    a*=2
ans.append(i)
a-=n
i=0
while a:
    if a%2:
        ans.append(i)
    i+=1
    a//=2
 
if len(ans)==1:
    print(*ans)
else:
    print(ans[0],*ans[1:][::-1])

 

E번 캣타워 돌리기

https://www.codetree.ai/problems/rotate-cat-tower/description

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

 

아이디어는 내가 냈고, 문제 제작은 다른분이 맡아주셨다. 매번 KAUPC에서 날 좌절시킨 문제들은 구현 문제였다. (21년 졸업사진, 22년 비행기 전시 두 문제다 대회 끝나고도 못풀었다.) 그리고 대회 특성상 구현에서 말리면 답이 없는걸 알기에 최대한 지문도 이해하기 쉽고, 로직도 간단하게 줬다고 생각했었다. 물론.. 스코어보드에선 그렇지 않다는게 보이긴 했지만 ㅠㅠ..

단순 회전 + 단순 중력 이 두 가지만 하면 풀리는 문제이다. N*M이 아니라 그냥 N*N으로 할걸 그랬다는 생각이 조금 들었다. 대회 끝나고 간단하게 구현해봤다.

 

from sys import stdin
input=stdin.readline

def rotate_r(arr):
    narr=[[0]*len(arr) for i in range(len(arr[0]))]
    for i in range(len(arr)):
        for j in range(len(arr[0])):
            narr[j][~i]=arr[i][j]
    return narr

def grav():
    for j in range(len(arr[0])):
        for i in range(len(arr)-1,-1,-1):
            if arr[i][j]!=0:
                continue
            for k in range(i-1,-1,-1):
                if arr[k][j]==2:
                    break
                if arr[k][j]==1:
                    arr[i][j],arr[k][j]=arr[k][j],arr[i][j]

n,m=map(int,input().split())
arr=[list(map(int,input().split())) for i in range(n)]
q=int(input())

for _ in range(q):
    if int(input())==1:
        arr=rotate_r(arr)
    else:
        for i in range(3):
            arr=rotate_r(arr)
    grav()
    
for i in arr:
    print(*i)

 

사실 우회전이나 좌회전 중 하나만 구현하면 된다! (일부로 시간복잡도 굉장히 널널하게 줬다)

하나 구현하고 그걸 3번 하면 반대 회전이 된다. 대회 당일날 제출한 코드를 볼 수 있다면 특별상 줄 때 이렇게 푼 사람이 있다면 그사람을 줘야겠다는 생각을 하고있었다.

 

H번 차이를 최대로!

https://www.codetree.ai/problems/make-dif-max/description

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

 

이 문제는 내가 낸 문제고, 원래는 O(N) 풀이만 통과시켜주려 했던 문제... 지만 현실적인 어려움으로 제한을 크게 완화했다. 대회 당시에 정말 신기하게도 4번까지 풀고 쭉쭉 넘기고 이 문제를 도전하시는 분들이 굉장히 많았다. 원래 마지막 문제로 할 계획이었던 만큼, 많이 완화했다고 해도 쉽지 않은 문제였을 텐데 그래도 생각보다 많은 분이 풀어주셨다.

 

최종적으로 풀이는 크게 4가지 정도 생각하고 있었다. 루트 N개씩이나 그룹으로 나누어서 조금 빠르게 해결, 우선순위 큐를 이용해서, 세그먼트 트리를 활용해서, 덱을 활용해서 이렇게 4개 정도 생각하고 있었다.

 

우선순위 큐를 활용한 풀이

from sys import stdin
from heapq import *
input=stdin.readline

n,k=map(int,input().split())
arr=list(map(int,input().split()))
mxhq=[]
mnhq=[]
ans=[0]*n

for i in range(k):
    heappush(mnhq,(arr[i],i))
    heappush(mxhq,(-arr[i],i))

ans[0]=abs(-mxhq[0][0]-mnhq[0][0])

for i in range(k,n+k-1):
    v=arr[i%n]

    heappush(mnhq,(v,i))
    heappush(mxhq,(-v,i))

    while mnhq and mnhq[0][1]<=i-k:
        heappop(mnhq)

    while mxhq and mxhq[0][1]<=i-k:
        heappop(mxhq)
    
    ans[i-k+1]=abs(-mxhq[0][0]-mnhq[0][0])

print(*ans)

어찌되었던 맨 앞에 최소 최대 둘 중 하나가 오는 우선순위 큐가 있을 것이고, 그 값이 범위를 벗어나면 pop 해주는 식으로 풀면 되는 문제였다.

 

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

n,k=map(int,input().split())
arr=list(map(int,input().split()))
ans=[0]*n

mnq=deque([(arr[0],0)])
mxq=deque([(arr[0],0)])

for i in range(1,k):
    if mnq[-1][0]<arr[i]:
        mnq.append((arr[i],i))
    else:
        while mnq and mnq[-1][0]>=arr[i]:
            mnq.pop()
        mnq.append((arr[i],i))
    if mxq[-1][0]>arr[i]:
        mxq.append((arr[i],i))
    else:
        while mxq and mxq[-1][0]<=arr[i]:
            mxq.pop()
        mxq.append((arr[i],i))

ans[0]=abs(mxq[0][0]-mnq[0][0])

for i in range(k,n+k-1):
    v=arr[i%n]
    if i-mnq[0][1]>=k:
        mnq.popleft()
    if mnq[-1][0]<v:
        mnq.append((v,i))
    else:
        while mnq and mnq[-1][0]>v:
            mnq.pop()
        mnq.append((v,i))
    if i-mxq[0][1]>=k:
        mxq.popleft()
    if mxq[-1][0]>v:
        mxq.append((v,i))
    else:
        while mxq and mxq[-1][0]<=v:
            mxq.pop()
        mxq.append((v,i))
    ans[i-k+1]=abs(mxq[0][0]-mnq[0][0])

print(*ans)

원래 의도했던 풀이, 덱을 활용해서 덱 내부를 단조 증가/감소로 구성시켜주면 된다.

 

I번 조상 노드

https://www.codetree.ai/problems/node-ancestor/description

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

이번 대회에서 유일하게 한 분이 푸신 문제다.

 

의도한 풀이는 트리 순회의 특성을 이용해서 푸는 문제로 DFS 1번으로 해결할 수 있는 문제이다. 이전 문제도 그렇고 지문이 짧고 뭘 해야 하는지 파악이 쉬워서 그런지 이 문제도 많은 분들이 도전한 문제다. 전위 순회 순서와 후위 순회 순서를 비교해서 풀어주면 된다. LCA를 막는 게 어렵기도 하고, 저렇게 푸는게 log 시간복잡도의 LCA보다 쉽다고 생각해서 LCA를 이용해 푸는 것도 맞도록 제한을 잡았다.

 

import sys
sys.setrecursionlimit(100001)
input = sys.stdin.readline

index = 0

n = int(input())
tree = [[] for _ in range(n + 1)]
in_time = [0] * (n + 1)
out_time = [0] * (n + 1)
in_t = 0
out_t = 0

def dfs(now):
    global in_t, out_t
    in_t += 1
    in_time[now] = in_t
    for nxt in tree[now]:
        dfs(nxt)
    out_t += 1
    out_time[now] = out_t

for _ in range(n - 1):
    a,b= map(int,input().split())
    tree[a].append(b)

dfs(1)

q = int(input())
results = []
for _ in range(q):
    a,b=map(int,input().split())
    if in_time[a] < in_time[b] and out_time[b] < out_time[a]:
        results.append("1")
    else:
        results.append("0")

print(" ".join(results))

 

J번 문제 따릉이와 킥보드

https://www.codetree.ai/problems/bycicle-n-kickboard/description

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

 

대망의 마지막 문제다. 딱 한 분 도전하셨는데 대회 종료후 간단하게 얘기할 기회가 생겨서 들어봤는데 플로이드 와샬 2번까진 잘 접근 하셨는데 아마 어디서 조금 실수가 있지 않으셨나 싶다. 만약 푸셨다면 대회 모든 문제가 한명씩은 푼 사람이 존재했을 것이다. 결국 이 문제는 아무도 못 풀었으니.. 아마 N 조건 때문에 플로이드 와샬 문제를 좀 풀어보신 분들이라면 문제에 플로이드 와샬을 적용해야겠다라고 생각하는 것 까지는 쉽지 않았을까 싶다.

 

그런데 어제 한번 다시 풀어봤는데 개인적으로는 플로이드 와샬 풀이가 더 떠올리기 힘들었다. 플로이드 와샬을 한번 돌려준 뒤, 정류장에 속한 정점들간 거리를 적절히 나눠준 뒤 다시 플로이드 와샬을 돌려주면 되었다. 이렇게 풀면 확실히 플레가 맞지 않나 싶다.

 

다익스트라로 풀수도 있는데 나는 방문을 vi[탑승여부(0 걷기, 1 따릉이, 2 자전거)][노드] 이런 식으로 접근해서 다익스트라를 돌렸는데 좀 더 스마트 하게 풀 수 있을 것 같지만 아마 로직은 비슷하지 않을까 싶다. 분기가 많고 신경써야 할 부분이 많아서 (시작점이 정류장이라던가, 한 점이 두  종류의 정류장에 모두 속한다던가) 실수하기 쉬운 문제였다.

 

플로이드 와샬

from collections import defaultdict
from sys import stdin
from copy import deepcopy
input=stdin.readline

n,m,p,q=map(int,input().split())
graph=[[1e10]*(n+1) for i in range(n+1)]
for i in range(m):
    a,b,c=map(int,input().split())
    graph[a][b]=graph[b][a]=c*1000

for i in range(1,n+1):
    graph[i][i]=0

for k in range(1,n+1):
    for i in range(1,n+1):
        for j in range(1,n+1):
            if (graph[i][k] + graph[k][j] < graph[i][j]):
                graph[i][j]=graph[i][k] + graph[k][j]

p=list(map(int,input().split()))
s=list(map(int,input().split()))

mx=graph[1][n]
ngraph=deepcopy(graph)

for i in p:
    for j in p:
        if i!=j:
            ngraph[i][j]=graph[i][j]//4

for i in s:
    for j in s:
        if i!=j:
            ngraph[i][j]=min(ngraph[i][j],graph[i][j]//2)

for k in range(1,n+1):
    for i in range(1,n+1):
        for j in range(1,n+1):
            if (ngraph[i][k] + ngraph[k][j] < ngraph[i][j]):
                ngraph[i][j]=ngraph[i][k] + ngraph[k][j]

print(ngraph[1][n])

 

다익스트라

from sys import stdin
from collections import defaultdict
from heapq import *
input=stdin.readline
 
def dijk():
    vi=[[inf]*(n+1) for i in range(3)]
    hq=[(0,0,1)] # dist, ride (0:nothing, 1:quickboard 2:bicycle), nowlocate
    vi[0][1]=0
    if 1 in bstop:
        heappush(hq,(0,2,1))
        vi[2][1]=0
    if 1 in qstop:
        heappush(hq,(0,1,1))
        vi[1][1]=0
 
    while hq:
        dist,ride,now=heappop(hq)
        if vi[ride][now]<dist:
            continue
        for nxt in graph[now]:
            nxtdist=dist+graph[now][nxt]//(2**ride)
            if nxtdist<vi[ride][nxt]:
                vi[ride][nxt]=nxtdist
                heappush(hq,(nxtdist,ride,nxt))
            if nxt in bstop:
                if ride==0:
                    if nxtdist<vi[2][nxt]:
                        vi[2][nxt]=nxtdist
                        heappush(hq,(nxtdist,2,nxt))
                elif ride==2:
                    if nxtdist<vi[0][nxt]:
                        vi[0][nxt]=nxtdist
                        heappush(hq,(nxtdist,0,nxt))
                else:
                    if nxt not in qstop:
                        continue
                    if nxtdist<vi[2][nxt]:
                        vi[2][nxt]=nxtdist
                        heappush(hq,(nxtdist,2,nxt))
            if nxt in qstop:
                if ride==0:
                    if nxtdist<vi[1][nxt]:
                        vi[1][nxt]=nxtdist
                        heappush(hq,(nxtdist,1,nxt))
                elif ride==1:
                    if nxtdist<vi[0][nxt]:
                        vi[0][nxt]=nxtdist
                        heappush(hq,(nxtdist,0,nxt))
                else:
                    if nxt not in bstop:
                        continue
                    if nxtdist<vi[1][nxt]:
                        vi[1][nxt]=nxtdist
                        heappush(hq,(nxtdist,1,nxt))
                
 
    return vi
 
inf=float('inf')
n,m,p,q=map(int,input().split())
 
graph=[defaultdict(int) for i in range(n+1)]
 
for i in range(m):
    a,b,c=map(int,input().split())
    graph[a][b]=graph[b][a]=c*1000

bstop=set(map(int,input().split()))
qstop=set(map(int,input().split()))
vi=dijk()
ans=vi[0][n]
print(ans)