[백준/C++] 마법천자문 (No. 23325)

문제

문제 설명

 

 

풀이

 

[문제 풀이]

 

이 문제는 모든 경우에 대해 계산을 하게되면 매우 많은 경우가 발생하므로 다른 방법으로 풀어야 한다.

 

이때, 잘 생각해보면 우리가 원하는 값은 최대 값이므로 특정부분까지 계산하는 방법이 매우 다양해도 최대값만 고려하고 다른 방법은 고려하지 않아도 된다는 것을 알 수 있다.

 

그러므로 이를 이용해 DP로 해결했다.

 

푸는 방법은 간단하다.

 

DP[i] = i번까지 계산한 방법 중 최대값 으로 정의한다.

 

그러면 DP[i] 뒤에 이어지는 연산을 생각해보면 i+1은 무조건 연산자가 된다.

 

그리고 i+2는 무조건 숫자기 때문에 아래와 같이 표현할 수 있다.

DP[i+2] = max(DP[i+2], DP[i] (+ or -) str[i+2])

 

그리고 고려해야하는 경우가 하나 더 있다.

 

i+2가 '+'라면 i+3이 '-'일 때,  DP[i+3] = max(DP[i+3], DP[i] (+ or -) 11) 인 경우를 고려하면 된다.

 

이렇게 계산을 마치고 나면 DP배열의 마지막에 연산의 최대 값이 저장되므로 출력하면 된다.

 

 

[아이디어 정리]

1. DP[i]를 i번까지 연산을 마친 경우의 최대값으로 정의한다.
2. 순서대로 규칙에 따라 DP를 갱신하며 DP배열의 값을 채운다.
3. 계산이 끝난 후 DP배열의 마지막에 저장된 값을 출력한다.

 

 

#include <string>
#include <vector>
#include <map>
#include <iostream>
#include <queue>
using namespace std;


int INF = -987654321;
void calc(string &str, int i, vector<int> &DP) 
{
    if (i + 2 >= str.size()) {
        return;
    }
    if (DP[i] == INF) {
        return;
    }

    if (str[i + 1] == '-') {
        if (str[i + 2] == '+') 
        {
            if (i + 3 < str.size()&&str[i+3]=='-')
            {
                DP[i + 3] = DP[i] - 11;
            }
            DP[i + 2] = max(DP[i + 2], DP[i] - 10);
        }
        else 
        {
            DP[i + 2] = max(DP[i + 2], DP[i] - 1);
        }
    }
    else
    {
        if (str[i + 2] == '+')
        {
            if (i + 3 < str.size() && str[i + 3] == '-')
            {
                DP[i + 3] = DP[i] + 11;
            }
            DP[i + 2] = max(DP[i + 2], DP[i] + 10);
        }
        else
        {
            DP[i + 2] = max(DP[i + 2], DP[i] + 1);
        }
    }
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    string str;
    cin >> str;
    vector<int> DP(str.size()+1, INF);
    if (str.size() > 1) {
        if (str[0] == '-')
            DP[0] = 1;
        else
        {
            if (str[1] == '-') {
                DP[1] = 11;
            }
            DP[0] = 10;
        }
    }
    else {
        if (str[0] == '-')
            DP[0] = 1;
        else
            DP[0] = 10;
    }
    for (int i = 0; i < str.size(); i++) {
        calc(str, i, DP);
    }
    cout << DP[str.size() - 1];

    return 0;
}

---

 

처음에 생각없이 DFS로 풀고 시간초과가 났다;

 

이후 최대값을 이용하면 되겠다는 생각에 BFS로 풀었는데 당연하게도 queue에 들어있는 값들의 index가 동일하지 않기 때문에 DFS랑 별 차이가 없었다 (11이 있기 때문에 index가 밀려서)

 

터무니 없게 풀었다는 생각에 DP로 풀어서 해결했다 

 

요즘 집중이 안된다고 너무 대충 풀었네...

 

 

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