KOI 2021 2차 후기/풀이

아쉬우면서 괜찮은 결과인 거 같다.  3,4번 테케를 못 긁어서 200으로 끝났는데 그래도 1번이 dp인데 풀었다는 거와 못해도 동상은 받으니 처음 본선치곤 잘 본 거 같다는 생각이 든다(19만 원 3동 ㅋㅋㅋ)

처음에 1번을 풀다가 맞왜틀 했다가 한 가지 처리를 안 해줬다는 거를 알고 해 줬는데 그 조그마한 실수 때문에 10분 정도를 날렸고

2번은 생각은 쉬웠는데 구현이 잘 안돼서 3시간 이상을 날렸다 그다음 3번에서 조금만 긁고 4번을 갈려고 했는데 1점도 안 긁혀서 계속하다가 결국엔 200점으로 끝났다 

 

1. 계산 로봇

위에서 말했던거처럼 dp다 어떤 점 (a, b)가 있을 때(y, x 순) |a-i|<=b-j를 만족하는(i, j)중 최댓값에다가 입력으로 들어오는 input [i][j] 값을 더하면 되는데 이때 마지막에는 input [i][j]를 빼줘야 된다.

|a-i|<=b-j 이거를 잘 생각해보면 (a, b)와 (i, j)의 y거리보다 x거리가 더 커야 된다는 걸 알 수 있다 즉 (a, b) 위치를 기준으로 왼쪽으로 삼각형 부분이 만족하는 부분이다.

빨간 사각형을 (a, b)라고 했을 때 파란색 부분이 위 식을 만족하는 부분이다.

피라미드 형태로 커져야 되기 때문에 dp [i][j]=max([(i-1, j-1), (i, j-1), (i+1, j-1)])+input [i][j] 이렇게 해주면 100점을 받게 된다.

import sys
sys.setrecursionlimit(10**9)
input=sys.stdin.readline
a,b=map(int,input().split())
l=[]
for i in range(a):
	c=list(input().strip())
	for g in range(b):c[g]=int(c[g])
	l.append(c)
#print(l)
dp=[[0 for i in range(2002)]for g in range(2002)]
for g in range(b):
    for i in range(a):
        if g==0:
            dp[i][g]=l[i][g]
        else:
            dp[i][g]=dp[i][g-1]
            if i!=0:dp[i][g]=max(dp[i][g],dp[i-1][g-1])
            if i!=a-1:dp[i][g]=max(dp[i][g],dp[i+1][g-1])
            dp[i][g]+=l[i][g]
ans=0
for i in range(a):ans=max(ans,dp[i][b-1]-l[i][b-1])
print(ans)

 

2. 누적 거리

이 문제는 지점 x [i]가 있고 그 지점에 사람 a [i] 명이 있을 때 Q개의 위치가 들어오면 모든 x [i]에서 위치로 가는데 거리는 찾으면 되는 문제인데 대신 x [i] 위치에서 입력 위치까지의 거리에 *a [i]도 해줘야 되는 문제이다.

 

X(지점 위치)		-10	6	-4	11
A(사람수)		1	4	3	2

이런 입력이 있다고 하자 이제 이 입력을 수직선에 그려보면

 

이렇게 나온다(x1=x [1])

그다음에 Q=1이고 2라는 입력이 들어왔고 입력으로 들어온 값을 x라고 정하자

일단 처음에 정렬된 값들 중 x보다 작거나 같은 값의 위치를 구해준다

lower_bound 써서 구해줄 수 있다.

그리고 그 위치를 t라고 정하자 이제 x를 기준으로 왼쪽 오른쪽을 나눌 것이다.

왼쪽부터 해보자

일단 필요한 게 있는데 바로 왼쪽 점부터 오른쪽 끝까지 오른쪽 점과의 거리를 구해주고 또 그 거리를 prefix sum(누적합)을 해준다.(배열은 ps로 해주자)

이제 가장 오른쪽 점부터 t까지의 거리*사람 수를 해주면 되는데

아까 거리에 대한 누적합을 만들어 줬으니 그걸 사용해보자

점 x1에서 t까지의 거리는 ps [t]-ps [점 x1의 순서-1]이다. 여기서 순서는 1부터 이고 ps [0]=0이다.

이때 거리는 6이고 점 x1의 a [1]는 1 이므로 6*1만큼을 사용하여 t까지 움직일 수 있다.(a는 1부터 시작)

왼쪽 점이 1개라 감이 안 잡힐 수 있겠지만 t를 모른다고 했을 때 

 

ps [t]*a [0]+(ps [t]-ps [1])*a [1]+(ps [t]-ps [2])*a [2]+.... ps [t]-ps [t-1])*a [t-1]

이게 모든 점에서 t까지 가는 이동거리이다.

이 식은 prefix sum을 안다면 외 그런지는 알 수 있을 것이다.

이제 이걸 중1 때 배우는 걸 사용해보자 t=3라고 했을 때

ps [3]*a [0]+(ps [3]-ps [1])*a [1]+(ps [3]-ps [2])*a [2]

가 된다. 여기서 식을 바꿔 보면

ps [3]*(a [0]+a [1]+a [2])-ps [1]*a [1]-ps [2]*a [2]가 된다.

이쯤 되면 방법이 보이는 사람도 있을 것이다.

t가 3일 때 a [0]+a [1]+a [2]이고 t가 4일 때는 a [3]를 더 더해주고 ps [3]을 ps [4]로 바꾼 뒤에 ps [3]*a [3]를 빼주면 된다.

가장 위에 있는 식도 바로 위에 있는 식처럼 바꾸면 ps [t]*sum(a [0~t-1])-ps [1]*a [1]-ps [2]*a [2]...-ps [t-1]*a [t-1]

이렇게 된다!

저식을 봤을 때 a(사람 수)의 구간합과 ps [i]*a [i]의 구간합이 필요하다는 걸 알게 된다.

하지만 아직 끝난 게 아니다. t까지만 움직였고 t에서 x까지 한 번 더 움직여야 한다.

이건 간단하다 t에서 x까지의 거리에 t위치까지의 사람 수를 곱해주면 된다.

이유는 너무 당연한 거니 설명은 안 하겠다. t 위치까지의 사람 수는 위에서 사람 수의 구간합을 만들어 줬기 때문에 그 구간합을 이용하면 된다.

이제 이렇게 나온 값을 더해주면 x를 기준으로 왼쪽에서의 이동거리는 모두 구한 것이다.

반대쪽도 다른 건 없으니 간단하게 반대쪽에서 시작하는 구간합을 만들어 줘도 되고 이미 만들어져 있는 구간합을 이용해도 된다. 그렇게 왼쪽 오른쪽 나온 값을 더해주면 모든 점에서 x까지의 이동거리가 된다.

 

 

3. 일이 이어져야 좋다

못 풀었다ㅜ

 

4. 공통괄호 문자열 사전

못 풀었다ㅜ

 

dp를 풀어서 나름 기쁘기도 하고 20점 정도를 못 긁은 게 아쉽기도 하지만 처음 본선 치고는 나쁘지 않다고 생각하고 앞으로 더 열심히 해서 언젠가 금상을 타길 빌면서 글을 마치겠다.

지금까지 koi 준비하고 보신 모든 분들 수고하셨습니다.