fragment-header
fragment-markdown
홈
로그인
로그아웃
내 블로그
설정
로그인
백준 23815 (C++) 똥게임
최초 업로드: 2025-11-20 00:53:53
최근 수정 시간: 2025-11-20 00:53:53
게시자: rlatjwls3333
카테고리: 백준
조회수: 4
# [Gold IV] 똥게임 [문제 링크](https://www.acmicpc.net/problem/23815) ## 문제 설명 <p style="text-align: center;"><img alt="" src="https://upload.acmicpc.net/45117fb9-7986-4866-aaa9-86b15864b606/-/preview/" style="width: 400px; height: 405px;"></p> <p>이 게임은 똥냄새가 너무 나서 도저히 볼 수가 없다! 따라서 당신은 직접 똥게임을 하지 않고 프로그램한테 똥게임을 시킬 것이다. 처음에는 사람 1명으로 시작한다. 당신에게는 총 $N$번의 턴이 주어지며, 각 턴마다 다음 선택지 4개중 2개가 주어진다. 같은 선택지가 주어질 수도 있다. 각 선택지는 $+x, -x, *x, /x \, (1 \leq x \leq 9)$ 중 하나로 주어진다.</p> <ol> <li>$+x$를 선택할 경우, 사람의 수가 $x$명만큼 증가한다.</li> <li>$-x$를 선택할 경우, 사람의 수가 $x$명만큼 감소한다.</li> <li>$*x$를 선택할 경우, 사람의 수가 $x$배가 된다.</li> <li>$/x$를 선택할 경우, 사람의 수가 $x$만큼 나눠진다. 만약 현재 사람 수가 x로 나눠지지 않을 경우 나머지는 버린다.</li> </ol> <p>$N$개의 선택지 중 <strong>1번에 한해</strong> 광고를 보고 <strong>선택지를 건너뛸 수 있다.</strong> 광고를 보지 않고 선택지를 건너뛰지 않아도 된다. 만약 각 턴이 끝난 뒤 현재 사람이 <strong>0명 이하</strong>가 되면 게임 오버가 된다. 당신은 $N$번의 선택지를 거친 후 사람의 수를 최대로 만들어야 한다. 어떠한 선택을 하더라도 중간에 사람의 수가 32비트 정수 범위를 넘지 않음을 보장한다.</p> ## 입력 <p>첫 번째 줄에 선택지의 개수 $N \, (1 \leq N \leq 100,000)$가 주어진다. </p> <p>그 이후 $N$개의 줄에 걸쳐 2개의 선택지가 공백을 사이로 두고 주어진다.</p> <p>각 선택지는 $+x, -x, *x, /x$ 중 하나로 주어진다 ($1 \leq x \leq 9$).</p> ## 출력 <p>$N$개의 선택지를 거친 후 최대 사람의 수를 출력한다. </p> <p>만약 어떤 선택을 하더라도 게임 오버가 된다면 ddong game을 출력한다.</p> ## 풀이 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]); } ```