[백준 23815번] 똥게임 (C++)

문제링크 : https://www.acmicpc.net/problem/23815

23815번: 똥게임

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MAX = 987654321;

ll n, dp[100001][2]; //건너뜀(1) 체크
string s1, s2;

ll func(int i, int flag, string s1, string s2)
{
    ll tmp1 = 0, tmp2 = 0;
    if(s1[0]=='+') tmp1 = dp[i-1][flag] + (s1[1]-'0');
    if(s2[0]=='+') tmp2 = dp[i-1][flag] + (s2[1]-'0');
    if(s1[0]=='-') tmp1 = dp[i-1][flag] - (s1[1]-'0');
    if(s2[0]=='-') tmp2 = dp[i-1][flag] - (s2[1]-'0');
    if(s1[0]=='*') tmp1 = dp[i-1][flag] * (s1[1]-'0');
    if(s2[0]=='*') tmp2 = dp[i-1][flag] * (s2[1]-'0');
    if(s1[0]=='/') tmp1 = dp[i-1][flag] / (s1[1]-'0');
    if(s2[0]=='/') tmp2 = dp[i-1][flag] / (s2[1]-'0');
    return max(tmp1, tmp2);
}

int main()
{
    ios_base::sync_with_stdio(0); 
	cin.tie(0);

    cin >> n;    
    dp[0][0] = dp[0][1] = 1;
    for(int i=1; i<=n; i++)
    {
        cin >> s1 >> s2;

        if(dp[i-1][0]>0) dp[i][0] = func(i, 0, s1, s2); //건너뛰지 않음
        if(dp[i-1][1]>0) dp[i][1] = max(dp[i-1][0], func(i, 1, s1, s2)); //건너뛴 것과 아닌 것 비교   
    }

    if(max(dp[n][0], dp[n][1])<=0) cout << "ddong game";
    else cout << max(dp[n][0], dp[n][1]);
    return 0;
}

 

건너뛰는 경우와 건너뛰지 않는 경우 이렇게 2가지에 대해 고려하면서 계산해야한다.

초기값은 사람 1명으로 시작한다고 했기에 처음부터 건너뛰는 경우, 처음에는 건너뛰지 않는 경우 둘 다 1로 초기화하고 시작한다.

 

건너뛰지 않는 경우는 주어진 계산을 직전값에 이어 그대로 해주면 된다.

다만 주의해야할 점은 계산 범위를 고려하여 (N=10만, 곱셈존재) long long으로 선언해주어야 하고,

문제에 주어진 조건에 따른 각 턴이 끝나고 현재 사람이 0명 이하일 시 게임오버를 고려하여야한다.

이를 위해 아직 계산전 값(현재 값)인 dp[i-1][0~1]의 값을 확인하여 0보다 큰지 아닌지를 체크해주어야 한다.

 

건너뛰는 경우에는 다음과 같이 2가지를 고려해주어야 한다.

건너뜀 -> 건너뜀 상태유지(이어서 진행)
-> 건너뜀 상태를 표시하고 값을 넣어 이어서 계산 (flag=1)

건너뛰지 않음 -> 건너뜀
-> 직전 값을 선택 (dp[i-1][0])

 

해당 문제에서 dp[i][0]을 건너뛰지 않은 상태, dp[i][1]을 건너뛴 상태로 표시했기에 이를 고려하여 건너뜀 상태를 체크한다.

문제에서 원하는 값은 최대값이기에 위 2가지 경우 중 더 큰 값을 선택하여 진행하게 된다.

 

계산과정을 위한 함수는 단순하게 작성했다.

받는 값은 현재 인덱스, 건너뜀 유무를 위한 flag, 부호와 숫자를 담은 문자열 2가지이다.

직전 값을 고려하여 현재 값을 계산해 반환해야하고, 만들어지는 값이 2가지 이므로 이를 위한 임시변수 2개를 사용한다.

각각에 대해 현재 부호가 무엇인지에 따라 문자를 숫자로 변환하여 계산을 더해준다.

문제에서 원하는 값은 최대값이기에 만들어진 임시변수 2가지 중에서 큰 값을 반환해주면 된다.

이때 flag 값이 0인지 1인지에 따라 현재 계산하는 값이 건너뛰지 않은 상태를 이어서 계산하는지, 건너뛴 상태에서 이어서 계산하는지를 알 수 있다.

 

 

생각보다 시간을 굉장히 많이 잡아먹은 문제인데, 범위를 고려하지 않아 int로 선언하고 풀었던 것도 있고,

무엇보다 각 턴이 끝나고 현재 사람이 0명 이하일 시 게임오버를 제대로 고려하지 않은 것을 너무 늦게 알아차렸다.