[Atcoder] ABC303 :: D - Shift vs. CapsLock

D - Shift vs. CapsLock

Caps를 누른 상태인지에 따라 2가지 케이스로 나눌 수 있는데, 이를 활용하면 다이나믹 프로그래밍으로 풀 수 있는 문제이다.
DP라는 것을 파악했다면 아주 간단하게 점화식을 세울 수 있는데, 이전 상태에 따라 caps가 켜졌는지, 꺼졌는지에 대해 2가지 케이스를 나누면 된다.

그리고 현재 입력해야 하는 문자열이 'A'인지 'a' 인지에 따라 최솟값을 갱신해 주면 된다.
약간의 함정은 꼭 z를 누르고 x를 눌러야 하는 것이 아니라는 점이다. z를 누르고 y를 눌렀을때 최솟값이 될 수 있으므로 이를 고려하여 점화식을 세워야 한다.

#include<iostream>
#include <algorithm>
#define INF 100000000000000
using namespace std;
typedef long long ll;

ll dp[2][300010];

int main()
{
    for (int i=0; i<300010; i++) {
        dp[0][i] = INF;
        dp[1][i] = INF;
    }
    
    ll x, y, z;
    string s;
    cin >> x >> y >> z;
    cin >> s;
    
    dp[0][0] = 0;
    
    for (int i=0; i<s.size(); i++) {
        char c = s[i];
        if (c == 'a') {
            dp[0][i+1] = min({dp[0][i] + x, dp[1][i] + y + z, dp[1][i] + x + z});
            dp[1][i+1] = min({dp[1][i] + y, dp[0][i] + x + z, dp[0][i] + z + y});
        } 
        
        if (c == 'A') {
            dp[0][i+1] = min({dp[0][i] + y, dp[1][i] + z + x, dp[1][i] + y + z});
            dp[1][i+1] = min({dp[0][i] + z + x, dp[0][i] + y + z, dp[1][i] + x});
        }
    }
    
    cout << min(dp[0][s.size()], dp[1][s.size()]) << '\n';
}