2023 KOI 예선 고1 결과

 

1교시를 완전히 망쳐서 가채점 나오기 전까지 0점도 가능할 거같다라는 생각을 했었는데 생각보다 40점이라는 높은? 점수가 나왔고 2교시는 작년보다는 어려웠지만 그렇게 많이 어려운 정도는 또 아닌지라 200점을 받고 총 240점이라는 점수로 전체 6.309%, 일반고 2.299% 로 은상 2개를 받으면서 본선을 가게 되었다.

 

import sys,math
inf=math.inf
input=sys.stdin.readline
a,b=map(int,input().split())
l=[list(map(int,input().split()))for i in range(a)]
t=[[0 for i in range(100)]for g in range(100)]
for i in range(a):
    for g in range(a):
        if i!=g:
            t[i][g]=abs(l[i][0]-l[g][0])+abs(l[i][1]-l[g][1])


if b==1:
    mn=inf
    for i in range(a):
        mx=-inf
        for g in range(a):
            if i!=g:
                mx=max(mx,t[i][g])
        mn=min(mn,mx)
if b==2:
    mn=inf
    for i in range(a):
        for g in range(a):
            if i!=g:
                mx=-inf
                for j in range(a):
                    mx=max(mx,min(t[i][j],t[g][j]))
                mn=min(mn,mx)

if b==3:
    mn=inf
    for i in range(a):
        for g in range(a):
            for j in range(a):
                if i!=g and g!=j and i!=j:
                    mx=-inf
                    for q in range(a):
                        mx=max(mx,min([t[i][q],t[g][q],t[j][q]]))

                    mn=min(mn,mx)
    
if mn==-inf:
    print(0)
else:
    print(mn)

    이 코드는 예선 1번코드인데 입력에서 주어지는 K의 범위가 1부터 3까지밖에 되지 않기 때문에 각 K 별 서로 다른 점들의 조합을 모두 계산해 가장 작은 걸 구해주면 된다. N 도 50이하 였기 때문에 50^4 도 문제없이 돈다.

 

import sys
sys.setrecursionlimit(10**7)
inf=200001
input=sys.stdin.readline
a,b=map(int,input().split())
graph=[[]for i in range(a+1)]
for i in range(a-1):
    c,d=map(int,input().split())
    graph[c].append(d)
    graph[d].append(c)

ans=0

def dfs(x,rn):
    global ans
    mx=-inf
    s_mx=-inf
    for i in range(len(graph[x])):
        if graph[x][i]!=rn:
            A=dfs(graph[x][i],x)+1
            if A>mx:
                s_mx=mx
                mx=A
            elif A>=s_mx:
                s_mx=A

    if mx>=b:
        ans+=1
        return -1

    if mx+s_mx>=b:
        ans+=1
        return -1

    if mx==-inf:
        return 0

    return mx

        
dfs(1,-1)
print(ans)

 이 코드는 2번 코드인데 74점까지 맞고 마지막에 메모리 초과가 난 코드이다.

방법은 특정 점을 루트 노드로 잡고 밑에서부터 올라오면서 거리가 K 가 될때마다 주유소를 설치해 주면 되는 문제이다. 대신 부모노드와 연결되어 있는 다른 노드와도 연결을 해야 되기 때문에 거리의 최댓값, 두 번째 최댓값을 구해서 두 값의 합을 비교해 주면서 진행하면 답을 구할 수 있다. 하지만 파이썬 함수를 사용했을 경우 메모리 초과가 나게 된다. 그러므로 이를 똑같이 c++로 바꿔서 작성해 주면 된다.

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll inf=200001;
ll a,b,c,d,ans=0,A=0;
vector<ll>graph[200010];

ll dfs(ll x,ll rn){
    ll mx=-inf;
    ll s_mx=-inf;
    for(int i=0;i<graph[x].size();i++){
        if(graph[x][i]!=rn){
            A=dfs(graph[x][i],x)+1;
            if(A>mx){
                s_mx=mx;
                mx=A;
            }else if(A>=s_mx){
                s_mx=A;
            }
        }
    }
    if(mx>=b){
        ans++;
        return -1;
    }
    if(mx+s_mx>=b){
        ans++;
        return -1;
    }
    if(mx==-inf)return 0;
    return mx;

}
int main(){
    cin <<
    scanf("%lld %lld",&a,&b);
    for(int i=0;i<a-1;i++){
        scanf("%lld %lld",&c,&d);
        graph[c].push_back(d);
        graph[d].push_back(c);
    }
    ans=0;
    dfs(1,-1);
    printf("%lld\n",ans);

}

   

자세한 풀이는 백준에 문제가 올라온다면 다시 하겠다.