[BOJ][🟡2][백준#01324] 젠장

문제 출처

BAEKJOON Online Judge #1324

문제

당신은 게임을 하다 걸려서 사회봉사를 해야 한다. 당신은 2일 동안 길 하나의 쓰레기를 주우려 한다. “이런 젠장” 매일 아침 첫 번째 쓰레기가 있는 위치에서 출발하여 N번째 쓰레기가 있는 위치까지 걸어가면서, 길에 놓여있는 쓰레기를 쓰레기 봉투에 담아야 한다. 모든 쓰레기를 주울 필요는 없으나, 걸어간 길을 되돌아갈 수는 없기 때문에 쓰레기는 항상 위치 순으로 주워야 한다. 그런데 쓰레기 봉투가 고물이라서 다음과 같은 제약이 있다.

첫째 날과 둘째 날 각각에 주운 쓰레기의 크기가 단조 증가해야 한다. 다시 말하면, 두 번째 또는 그 이후로 주운 쓰레기의 크기는 바로 전에 주운 쓰레기의 크기보다 크거나 같아야 한다. 각 날에 주운 쓰레기들의 개수와 크기는 완전히 같아야 한다.

예를 들어, 첫째 날에는 크기가 2, 3, 3, 4인 쓰레기를 차례로 주울 수 있지만, 크기가 4, 2, 3, 3인 쓰레기를 차례로 주울 수는 없다. 또한 첫째 날에 크기가 2, 3, 3, 4인 쓰레기를 주웠다면, 둘째 날에도 정확히 크기가 2, 3, 3, 4인 쓰레기를 주워야 한다. 당신은 특유의 예지력으로 오늘과 내일 길거리에 쓰레기가 어떤 식으로 놓여있을지 안다. 하루마다 최대 몇 개의 쓰레기를 주울 수 있을까?

입력

첫 번째 줄에는 쓰레기의 개수 N이 주어진다. (N ≤ 1,000) 두 번째 줄에는 첫째 날 쓰레기의 크기가 위치 순서대로 각각 N개 주어진다. 세 번째 줄에는 둘째 날 쓰레기의 크기가 위치 순서대로 주어진다. 쓰레기의 크기는 50,000보다 작거나 같은 자연수이다.

출력

하루마다 주울 수 있는 쓰레기의 최대 개수를 출력한다.

예제

입력

10
1 2 3 4 5 6 7 8 9 10
1 3 5 7 9 2 4 6 8 10

출력

6

My Sol

N = int(input())
day1 = [0]+list(map(int, input().split()))
day2 = [0]+list(map(int, input().split()))
set_day2 = set(day2)
ret = [set() for _ in range(N+1)]
ret[0].add((0, 0))

for i in range(1, N+1):
    ret[i] = ret[i-1]
    cur_v = day1[i]
    if cur_v not in set_day2: continue

    add_list = set()
    for tupp in ret[i]:
        mi, ms = tupp
        if day2[mi] >= cur_v: continue

        for ii in range(mi+1, N+1):
            if day2[ii] != cur_v: continue

            add_list.add((ii, ms + 1))

    check_obj = {}
    for k, v in add_list:
        ov = check_obj.get(k)
        if ov and ov >= v: continue
        check_obj[k] = v

    for k, v in check_obj.items():
        ret[i].add((k, v))

    if not i%10:
        clean = dict()
        for idx, cnt in ret[i]:
            if clean.get(cnt, []):
                clean[cnt].append([idx, day2[idx]])
            else:
                clean[cnt] = [[idx, day2[idx]]]

        max_cnt = max(clean.keys())
        tmp = set()
        for cnt, arrs in clean.items():
            if (N - i) + cnt < max_cnt: continue
            arrs.sort(key=lambda x: (x[1], x[0]))

            cur_val = -1
            for idx, val in arrs:
                if val == cur_val: continue
                cur_val = val
                tmp.add((idx, cnt))

        ret[i] = tmp

ans = 0
for sett in ret[N]:
    if ans < sett[1]:
        ans = sett[1]

print(ans)

문제에 오류가 있어 해결하지 못했다가 질문을 통해 해결한 문제였다. 오류는 monotonic 증가가 아닌 strictly 증가, 즉 이전까지 주운 쓰레기와 크거나 같은 것이 아니라, 크기만 해야하는 것이다. DP를 이용한다.

1. 입력을 처리한다.
2. Day1을 기준으로 이 날 쓰레기를 주울지, 줍지 않을지에 따라 DP가 확장되는 방식이다.
3. 만약 Day1의 어떠한 날이 Day2의 쓰레기 리스트에 없다면 주워도 의미가 없으므로 continue
4. 이전까지 주울 수 있는 모든 경우의 수 중 ret[i-1]에서 가져왔고, 이를 하나하나 까본다.
5. Day1의 특정 쓰레기를 주웠을 경우 이전까지의 쓰레기를 줍는 경우에서 이보다 같거나 큰 쓰레기를 주웠다면 continue
6. 현재까지의 쓰레기 크기가 현재 쓰레기보다 작은 경우 직전의 쓰레기를 주운 날 이후로 가장 가까운 날의 인덱스를 임시 set인 add_list에 추가해준다.
7. 같은 쓰레기의 개수라면 더 작은 쓰레기, 더 빨리 주울수록 이득이므로 그에 대한 처리를 해줘 최적의 쓰레기를 ret[i]에 넣는다.
8. 이렇게 된다면 기하급수적으로 set이 많아지므로 10개 단위마다 최적의 경우를 제외한 나머지를 제거해준다.
9. 마지막 ret[N]의 모든 set에서 모아온 쓰레기의 개수 중 최댓값을 출력한다.

결과

맞았습니다!!

모범답안

출처

import sys
input = sys.stdin.readline

N = int(input())
lst1 = [0] + list(map(int, input().split()))
lst2 = [0] + list(map(int, input().split()))

dp = [0] * (N + 1)
max_cnt = 0
for i in range(1, N + 1):
    cnt = 0
    for j in range(1, N + 1):
      # 첫날 쓰레기와 둘째날 쓰레기가 일치하면
        if lst1[i] == lst2[j]: 
            dp[j] = max(dp[j], cnt + 1)
        # 둘째날 쓰레기를 선택했다면, 다음에 첫째날에 선택하는 쓰레기는 둘째날 선택했던 쓰레기보다 커야함
        if lst1[i] > lst2[j] and dp[j] > cnt: 
            cnt = dp[j]
        max_cnt = max(max_cnt, dp[j])
print(max_cnt)

DP를 이용해 너무나 쉽게 풀은 코드를 분석해보려 한다. 풀이 시간은 나의 1/15이고, 코드 양도 절반 수준이다.