[Python] 23815번 똥게임

 

 

https://www.acmicpc.net/problem/23815

23815번: 똥게임

 

---

 

22/11/17

 

 

그리디와 DP를 섞은 문제로, 실수하기가 좋은 문제라고 생각한다.

---

 

문제 접근 방식:

 

 

나는 문제에서 주어진 선택지 $N$개의 제한이 최대 $100,000$개라는 것에 주목하였다.

 

일단, 두 가지 선택지 중에서 선택을 할 때 항상 큰 것을 선택해야 된다는 점은 너무나도 당연한 사실이다.(그리디 적인 접근)

 

문제는 스킵을 최대 한 번까지 할 수 있다는 점이다.

 

 

여기서 DP를 사용해야 한다.

 

만약 DP적인 접근을 하지 않는다면, 우리는 각 선택지 별로 스킵을 하는 것을 전부 계산하고, 그리고 스킵을 안 한 것까지 계산을 해야 하므로, 이중으로 for문을 돌려야 한다.

 

다시 말해, 시간 복잡도가 $O(n^2)$이 된다.

 

우리는 $N$이 최대 $100,000$이라는 사실을 알고 있으므로, 이렇게 된다면 시간 초과가 날 것이 분명했다.

 

 

그래서 $O(n)$으로 풀 수 있는 방법을 구상했다.

 

맨 처음에는 DP를 사용하지 않고 그리디적으로 접근했다.

 

나는 각 선택지에서 항상 증가하는 쪽으로 선택을 하고 그때의 인원수를 리스트에 저장하는 방식으로 했다.

 

그리고 인원수가 제일 많이 떨어지는 때, 혹은 인원수가 음수가 되는 때를 스킵하는 때라고 정한 뒤에, 스킵을 했을 때의 값을 구했다.

 

이후, 스킵을 한 번도 하지 않은 값과 스킵을 했을 때의 값 둘 중에 큰 값을 출력하도록 했다.

 

그랬더니 틀렸습니다를 받았다.

 

 

그 이유는, 인원수가 제일 많이 떨어지는 때를 스킵한다고 해서 항상 최대가 된다고 보장할 수 없기 때문이다.

 

예를 들어, 스킵을 한 번도 하지 않았을 때의 선택지가 다음과 같다고 해보자.

 

$$+1, *3, /2, /3$$

 

그렇다면, 내가 했던 접근 방법으로 하자면 $/2$를 했을 때가 제일 많이 떨어지는 때 이므로 이 선택지를 스킵해야만 한다.

 

그러면 스킵을 한 번 했을 때의 최댓값이 $2$가 나오는데, 실제로는 $/3$을 스킵하는 것이 더 큰 값($3$)이 나온다.

 

 

나는 이 반례를 찾아내고 나선, DP와 접목해 DP값 for문을 돌려 계속하여 갱신하는 방식으로 하면 $O(n)$으로 찾아낼 수 있을 것이라고 생각했다.

 

나는 DP를 다음과 같이 정했다.

 

$$DP[0] = 지금까지 한 번도 스킵하지 않았을 때 최댓값$$ $$DP[1] = 스킵 한 번을 이미 사용했을 때 최댓값$$

 

그렇다면 $DP[0]$은 그냥 선택지 중에서 제일 크도록 만드는 값을 선택하여 그 값으로 갱신하면 그만이다.

 

나는 숫자와 선택지 두개를 입력받으면, 두 선택지 중에서 큰 값이 나오도록 하는 선택지를 선택하여 연산한 후 그 값을 내보내는 함수 $maxcal(number, a, b)$을 정의했다.

 

따라서, $DP[0]$은 항상 그냥 $maxcal(DP[0], a, b)$로 갱신해주면 된다.

 

 

$DP[1]$은 스킵을 이미 한 값 중 최댓값이므로, 이번 턴에 스킵을 하지 않고 그대로 유지하는 것($maxcal(DP[1], a, b)$)이 최대가 될 수도 있고, 이번에 새롭게 스킵을 하는 것($DP[0]$)으로 최댓값이 바뀔 수 있다.

 

따라서 $DP[1]$은 $max(maxcal(DP[1], a, b), DP[0])$으로 갱신해주면 된다.

 

 

주의해야 할 점은, 항상 최댓값이 나오도록 선택을 했음에도 불구하고 사람 수가 음수가 될 때는, 그런 거 상관없이 항상 스킵을 해줘야 된다는 점인데, 이는 $DP[0]$이 항상 0보다 클 때만 $DP[0]$을 갱신하는 것으로 해결할 수 있다.

 

$DP[0]$이 음수가 나온다면, 그땐 무조건 스킵을 할 수밖에 없기 때문에 $DP[0]$의 정의가 깨져버려 더 이상 갱신할 이유가 없기 때문이다.

---

아래는 내가 위의 접근 방식과 같이 작성한 파이썬 코드이다. 더보기를 누르면 확인할 수 있다.

# 23815번 똥게임
# 그리디, DP
'''
접근 방법:
어차피 최대로 만들기 때문에, 항상 늘어나도록 선택지를 정해보자
나이브한 풀이)
O(n^2)
DP적용한 풀이)
O(n)
'''
import sys
input = sys.stdin.readline

N = int(input())
def max_cal(num, a, b):
    m, n = 0, 0
    if a[0] == '+':
        m = num + int(a[1])
    elif a[0] == '-':
        m = num - int(a[1])
    elif a[0] == '*':
        m = num * int(a[1])
    else:
        m = num // int(a[1])
    if b[0] == '+':
        n = num + int(b[1])
    elif b[0] == '-':
        n = num - int(b[1])
    elif b[0] == '*':
        n = num * int(b[1])
    else:
        n = num // int(b[1])
    if m > n:
        return m
    else:
        return n

DP = [1, -20] # DP[0]은 스킵 지금까지 안했을 때 최댓값, DP[1]은 스킵 이미 했을 때 최댓값
'''
사람수가 이전보다 많아지면 스킵 이유가 없음
사람수가 이전보다 적어지면 두가지 경우가 생김
아직 건너뛰지 않은 경우 -> 건너뛰거나 그대로 간다
이미 건너뛴 경우 -> 그대로 간다
DP[0]를 저렇게 정의한다면, DP[0]는 갱신 될 때마다 계속 그냥 계산해주는거랑 똑같음
DP[1]을 저렇게 정의한다면, DP[1]은 두가지 경우가 생김
DP[1]을 갱신 안하고 그대로 유지(스킵을 이미 한 상태로 그대로 가기)
DP[1]을 이번 턴에 스킵하는 상태로 갱신(스킵을 이번턴에 하는 상태로 바꾸기)
따라서 두개 중 하나를 max함수 취해주면 된다.
'''
for i in range(N):
    a, b = input().rstrip().split()
    if DP[0] > 0:
        if_no_skip = max_cal(DP[0], a, b)
    if_already_skip = max_cal(DP[1], a, b)
    DP[0], DP[1] = if_no_skip, max(DP[0], if_already_skip)
    if max(DP) <= 0:
        print('ddong game')
        break
else:
    print(max(DP))