https://www.acmicpc.net/problem/2671
2671번: 잠수함식별
입력에 들어있는 스트링을 읽고, 이것이 잠수함의 엔진소리를 나타내는 스트링인지 아니면 그냥 물속의 잡음인지를 판정한 후, 잠수함의 엔진 소리에 해당하는 스트링이면 "SUBMARINE"을 출력하고
www.acmicpc.net
[난이도] 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
'Problem-Solving > BOJ' 카테고리의 다른 글
| [BOJ/백준][Gold5] 15971 : 두 로봇 (C++) (0) | 2022.01.23 |
|---|---|
| [BOJ/백준][Gold5] 7490 : 0 만들기 (C++) (0) | 2022.01.23 |
| [BOJ/백준][Gold5] 15591 : MooTube (Silver) (C++) (0) | 2022.01.23 |
| [BOJ/백준][Gold5] 14395 : 4연산 (C++) (0) | 2022.01.23 |
| [BOJ/백준][Gold5] 14728 : 락치기 (C++) (0) | 2022.01.23 |