[SWEA] 8676. 동현이와 한결이는 아이돌(c++) / dp

처음에는 전혀 감을 잡지 못하고 결국.. 다른 분의 코드를 약간 참고해서 구현했다.

dp를 사용하여 "SAMSUNG"을 dp[0]~dp[6]으로 잡아서

1) "S" 일때는 0, 3이니까

dp[0] = dp[0]+1;

dp[3] = dp[2]+dp[3]

2) "A"일때는 1이니까

dp[1] = dp[0]+dp[1]

....이런식으로 dp를 이용하면 된다.

 

코드 첨부

// 8676. 동현이와 한결이는 아이돌
#include <iostream>
#include <cstring>
#include <vector>
using namespace std;
 
int testcase;
string s;
int dp[7] = {0, };
vector<int> final;
const int MAX = 1000000007;
 
int main()
{
    cin>>testcase;
    for(int i=0; i<testcase; i++){
        memset(dp, 0, sizeof(dp));
        cin>>s;
        for(int j=0; j<s.size(); j++){
            if(s[j]=='S'){
                dp[0] = (dp[0]+1)%MAX;
                dp[3] = (dp[2]+dp[3])%MAX;
            }else if(s[j]=='A'){
                dp[1] = (dp[0]+dp[1])%MAX;
            }else if(s[j]=='M'){
                dp[2] = (dp[1]+dp[2])%MAX;
            }else if(s[j]=='U'){
                dp[4] = (dp[3]+dp[4])%MAX;
            }else if(s[j]=='N'){
                dp[5] = (dp[4]+dp[5])%MAX;
            }else if(s[j]=='G'){
                dp[6] = (dp[5]+dp[6])%MAX;
            }
        }
 
        final.push_back(dp[6]);
    }
 
    for(int i=0; i<final.size(); i++){
        cout<<"#"<<i+1<<" "<<final[i]<<"\n";
    }
}

 

문제 첨부

swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AW2Jo6bqABMDFATy&categoryId=AW2Jo6bqABMDFATy&categoryType=CODE

SW Expert Academy