랜덤 마라톤 코스(41,42)
지금까지 풀지 못했었던 랜덤 마라톤 문제들을 조금씩 풀어보려고 한다.
이전에 풀지 못했었던 코스 41,42의 골드 문제 4문제를 풀어보았다.
3/30 (일) 카페에서 약 2시간 이상 풀이를 하였다.
22862 가장 긴 짝수 연속한 부분 수열 (large)
Gold 5 난이도의 가장 긴 짝수 연속한 부분 수열을 구하는 문제이다.
문제를 보았을 때 유형 중 하나인 증가하는 부분 수열 결의 문제라고 생각하고 DP로 접근했다가 실패하고 문제 유형을 통해 투 포인터유형의 문제라는 것을 알고 투 포인터로 접근하였다.
해당 문제를 투포인터로 접근하는 방법을 생각해보자.
$s$와 $e$를 어떻게 이용할 것이냐가 투포인터의 정수라고 생각한다. 해당 문제의 성질을 보면 결국 가장 긴 길이를 구해야하는 것이 목표이며 이를 위해선 $e$는 끝까지 진행을 해야하며 $s$는 조건에 맞게 따라오는 Logic으로 구성해야 할 것이다.
만약 e가 앞으로 쭉쭉 진행을 하면서 해당 부분이 홀수라면 $cnt$를 1 올려주고 $cnt$가 조건에 맞는 K개 이상이 되었을 경우 해당 조건에 맞을 수 있을 때 까지 s를 증가시켜준다.
결국 구해야하는 가장 긴 짝수 연속한 부분 수열은 현재 길이 $e-s+1$에서 홀수의 개수 $cnt$를 빼준
\[result = (e-s+1-cnt)\]로 정의된다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
import sys
input = sys.stdin.readline
# 길이가 N인 수열 S
# 짝수로 이루어진 연속한 부분 수열 중 가장 긴 길이
n, k = map(int,input().split())
arr = list(map(int,input().split()))
s, e = 0,0
cnt = 0
ml = 0
while s <= e and e < n :
if arr[e] % 2 == 1 :
cnt += 1
while cnt > k :
if arr[s] % 2 == 1 :
cnt -= 1
s += 1
ml = max(ml, e-s+1-cnt)
e += 1
print(ml)
2240 자두나무
Gold 5난이도의 T초동안 최대 W번 움직이며 받을 수 있는 자두의 최대 개수를 출력하는 문제이다.
문제 의도 자체는 DP라는게 명확히 보이는 문제였지만 점화식을 처음에 명확히 파악하는게 어려웠었다.
dp를 설정할 때 i,j,k를 다음과 같이 설정하였다.
- i : N초
- j : W번 자리 이동
- k : 현재 자리 (1 or 2)
만약 현재 자리와 떨어지는 자두의 자리와 같다면 다음 점화식과 같다.
\[dp[i][j][k] = dp[i-1][j][k] + 1\]만약 현재 자리와 떨어지는 자두의 자리가 다르다면 점화식은 다음과 같다.
\[dp[i][j][k] = max(dp[i-1][j][k], dp[i-1][j-1][1-k] + 1)\]추가로 처음 자두는 1번 자두나무 아래에 위치해 있다는 것을 주의해야 한다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
import sys
input = sys.stdin.readline
n, w = map(int,input().split())
arr = [int(input()) for _ in range(n)]
cur = 1
dp = [[[0 for _ in range(2)] for _ in range(w+1)] for _ in range(n)]
if arr[0] == 1 :
dp[0][0][0] = 1
else :
dp[0][1][1] = 1
for i in range(1, n) :
for j in range(w+1) :
for k in range(2) :
if arr[i] == k + 1:
dp[i][j][k] = dp[i-1][j][k] + 1
else :
if j > 0 :
dp[i][j][k] = max(dp[i-1][j][k], dp[i-1][j-1][1-k] + 1)
else :
dp[i][j][k] = dp[i-1][j][k]
_max = 0
for i in range(n) :
for j in range(w+1) :
for k in range(2) :
_max = max(_max, dp[i][j][k])
print(_max)
5980 Corn Maze
Gold 4 난이도의 Grpah 탐색 문제이다. 딱봐도 BFS Search 문제이지만 주의 할 부분은 Slide라고 하는 경로 이동 Trigger가 추가 되었다는 것이다.
전체적으로 기본적인 BFS와 같이 시작점에서 이동할 수 있는 방향으로 이동한다. Slide Trigger를 만날 경우 해당 지점을 방문배열에 Check하고 도착하여 연결된 부분에서는 방문배열을 Check하지 않는다.
위와 같은 방법으로 해야하는 경우가 발생하게 되는데, 예를 들어 S -> S’로 이동하고 S’ -> S로도 이동이 가능해야 하는 경우가 있기 때문이다. 해당 반례는 아래와 같다.
6 6
###=##
#.WV##
#K####
#V.W##
#.K.@#
######
재미있는 문제인 것 같다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
import sys
from collections import defaultdict, deque
input = sys.stdin.readline
def bfs(i,j) :
q = deque()
q.append((i,j,0))
check[i][j] = True
while q :
x,y,cnt = q.popleft()
#print(x,y)
if (x,y) == end :
print(cnt)
exit()
for dx,dy in [(-1,0), (1,0), (0,-1), (0,1)] :
nx,ny = x+dx,y+dy
if 0<=nx<n and 0<=ny<m and maps[nx][ny] != '#' and not check[nx][ny] :
if maps[nx][ny].isalpha() :
lst = tp[maps[nx][ny]]
another = (0,0)
for px,py in lst :
if (px,py) != (nx,ny) :
another = (px,py)
check[nx][ny] = True
nx,ny = another
#check[nx][ny] = True
q.append((nx,ny, cnt+1))
else :
check[nx][ny] = True
q.append((nx,ny,cnt+1))
n, m = map(int,input().split())
maps = [list(map(str,input().strip())) for _ in range(n)]
check = [[False for _ in range(m)] for _ in range(n)]
tp = defaultdict(list)
start = (0,0)
end = (0,0)
for i in range(n) :
for j in range(m) :
if maps[i][j].isalpha() :
tp[maps[i][j]].append((i,j))
if maps[i][j] == '@' :
start = (i,j)
if maps[i][j] == '=' :
end = (i,j)
bfs(start[0], start[1])
29616 인기 투표
잘 몰겠다.. 어렵다… 접근법이… 어렵다…
Enjoy Reading This Article?
Here are some more articles you might like to read next: