[🥇4 / 백준 23815 / 파이썬] 똥게임

 

23815번: 똥게임

 

문제

이 게임은 똥냄새가 너무 나서 도저히 볼 수가 없다! 따라서 당신은 직접 똥게임을 하지 않고 프로그램한테 똥게임을 시킬 것이다. 처음에는 사람 1명으로 시작한다. 당신에게는 총 N번의 턴이 주어지며, 각 턴마다 다음 선택지 4개중 2개가 주어진다. 같은 선택지가 주어질 수도 있다. 각 선택지는 +x, −x, ∗x, /x (1≤x≤9) 중 하나로 주어진다.

1.  +x를 선택할 경우, 사람의 수가 x명만큼 증가한다.
2.  −x를 선택할 경우, 사람의 수가 x명만큼 감소한다.
3.  ∗x를 선택할 경우, 사람의 수가 x배가 된다.
4.  /x를 선택할 경우, 사람의 수가 x만큼 나눠진다. 만약 현재 사람 수가 x로 나눠지지 않을 경우 나머지는 버린다.

 N개의 선택지 중 1번에 한해 광고를 보고 선택지를 건너뛸 수 있다. 광고를 보지 않고 선택지를 건너뛰지 않아도 된다. 만약 각 턴이 끝난 뒤 현재 사람이 0명 이하가 되면 게임 오버가 된다. 당신은 N번의 선택지를 거친 후 사람의 수를 최대로 만들어야 한다. 어떠한 선택을 하더라도 중간에 사람의 수가 32비트 정수 범위를 넘지 않음을 보장한다.

입력

첫 번째 줄에 선택지의 개수 N (1≤N≤100,000)가 주어진다. 

그 이후 N개의 줄에 걸쳐 2개의 선택지가 공백을 사이로 두고 주어진다.

각 선택지는 +x,−x,∗x,/x 중 하나로 주어진다 (1≤x≤9).

출력

 N개의 선택지를 거친 후 최대 사람의 수를 출력한다. 

만약 어떤 선택을 하더라도 게임 오버가 된다면 ddong game을 출력한다.

 

예제 입력 1 3 +5 *2 +4 *2 -5 /2	예제 출력 1 12
예제 입력 2 3 +3 *6 -8 -9 -9 -9	예제 출력 2 ddong game

 

힌트

첫번째 예제에서는 +5, ∗2를 선택하고 3번째 선택지를 건너뛸 경우, 12명으로 최대가 된다.

두번째 예제에서는 어떤 선택지를 고르더라도 게임 오버가 된다.

 

풀이

 

두 선택지 중 무조건 사람이 더 많이 있게 되는 쪽을 골라야 한다.

따라서 두 선택지를 유심히 생각하기보단 그냥 계산했을 때 더 많이 있는 쪽만 고르면 된다.

 

만약 선택지를 고른 후의 사람의 수가 이전보다 많게 된다면 건너뛸 이유가 없다.

따라서 그대로 갱신해주면 된다.

 

사람의 수가 더 적어지게 되었을 때의 경우를 잘 생각해야 한다.

아직 건너뛰지 않았다면 건너뛰어도 되고, 그대로 진행할 수도 있다.

이미 건너뛰었다면, 그대로 진행하는 수밖에 없다.

 

여기서, 건너뛰기를 한 경우와 건너뛰지 않은 경우로 나누어 생각한다.

건너뛰기를 아직 하지 않은 경우를 p0, 이미 한 경우를 p1라고 가정한다.

 

p0의 경우 그냥 계산 결과값만 담는다. 말 그대로 건너뛰지 않은 경우이기 때문이다.

p1의 경우 그대로 진행했을때의 결과와, 직전의 p0값 중 큰 것을 고르면 된다.

이전 턴의 p0에서 점프하여 현재 p1의 결과가 될 수 있기 때문이다.

 

p0의 경우 유의해야 할 것이 만약 0보다 작아진 경우 계산 결과값을 갱신하면 안 된다.

 

import sys
input = sys.stdin.readline

def cal(s,a,b):
    if s == "+": return a+b
    elif s == "-": return a-b
    elif s == "*": return a*b
    else: return a//b

n = int(input())
p = [1,-10]

for _ in range(n):
    a,b = input().rstrip().split()
    if p[0] > 0:
        c = max(cal(a[0],p[0],int(a[1])),cal(b[0],p[0],int(b[1])))
    d = max(cal(a[0],p[1],int(a[1])),cal(b[0],p[1],int(b[1])))
    
    p[1] = max(p[0],d)
    p[0] = c
    if max(p) <= 0:
        print("ddong game")
        break
else:
    print(max(p))