백준 23815 (C++) 똥게임

최초 업로드: 2025-11-20 00:53:53

최근 수정 시간: 2025-11-20 00:53:53

게시자: rlatjwls3333

카테고리: 백준

# [Gold IV] 똥게임

[문제 링크](https://www.acmicpc.net/problem/23815)

## 문제 설명

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

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

## 입력

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

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

각 선택지는 $+x, -x, *x, /x$ 중 하나로 주어진다 ($1 \leq x \leq 9$).

## 출력

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

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

## 풀이
dp[i][j]를 i번째 선택지까지 j번 건너뛰었을 때의 최대 사람 수로 두고 풀었습니다.

``` c++
#include<bits/stdc++.h>
using namespace std;

int dp[100'001][2];

int calc(int val, string s) {
    int x = s[1]-'0';
    if(s[0]=='+') return val+x;
    else if(s[0]=='-') return val-x;
    else if(s[0]=='*') return val*x;
    return val/x;
}

int main() {
 ios::sync_with_stdio(0); cin.tie(0);
 int n; cin >> n;
 dp[0][0]=1;
 for(int i=1;i<=n;i++) {
 string a, b; cin >> a >> b;
 if(dp[i-1][0]>0) {
 dp[i][0] = max(calc(dp[i-1][0], a), calc(dp[i-1][0], b));
 dp[i][1] = dp[i-1][0];
 }
 if(dp[i-1][1]>0) dp[i][1] = max(dp[i][1], max(calc(dp[i-1][1], a), calc(dp[i-1][1], b)));
 if(dp[i][0]<=0 && dp[i][1]<=0) {
 cout << "ddong game";
 return 0;
 }
 }
 cout << max(dp[n][0], dp[n][1]);
}
```