[BOJ/백준][Gold5] 2671 : 잠수함식별 (C++)

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

2671번: 잠수함식별

 

 

[난이도] Gold5
[유형] DP

[풀이]
정규표현식을 이용하면 간단히 해결할 수 있지만 평소 사용하지 않던 문법이라
다이나믹 프로그래밍을 이용하여 해결했습니다.

top-down DP를 이용하였습니다
dp[n] : 부분 문자열 s[n..s.size()-1] 이 SUBMARINE이면 1, NOISE이면 0을 return

s[n..n+1] 이 "01"인 경우와
s[n..n+2] 이 "100"인 경우로 나누어서 해결해주면 됩니다.

"01"인 경우 한가지 케이스밖에 없으므로 sol(n+2)를 호출하여 0인지 1인지 확인해주면 됩니다.

"100"인 경우 10001...,100001... 와 같은 케이스가 가능하므로 1이 언제 처음 등장하는지 체크해 준 뒤
만약 '1'이 i부터 등장한다면 i부터 1이 등장할 때까지 sol(i+1),sol(i+2),sol(i+3)...을 '0'이 등장하기 전까지
계속 호출해주며 return 값이 1이 나온다면 정답이므로 종료해줍니다.

 

#include <cstdio>
#include <cstring>
#include <iostream>
#include <string>
using namespace std;
string s;
int dp[151];
int sol(int n){
    if(n==s.size()) return 1;
    int& ret = dp[n];
    if(ret!=-1) return ret;

    if(n>=s.size()-1) return ret=0;
    string t = s.substr(n,2);

    if(t=="01" && sol(n+2)) return ret=1;
    if(n>=s.size()-3) return ret=0;
    t = s.substr(n,3);

    if(t=="100"){
        int i;
        for(i=n+3;i<s.size();i++){
            if(s[i]=='1') break;
        }
        for(int j=i;j<s.size();j++){
            if(s[j]!='1') break;
            else if(sol(j+1)) return ret=1;
        }
    }
    return ret=0;
}
int main(){
    cin >> s;
    memset(dp,-1,sizeof(dp));
    if(sol(0)) cout << "SUBMARINE";
    else cout << "NOISE";
}

https://github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Gold5/2671.cpp