[백준/실버1] 백준 28117번 prlong longf - c++ (dp)

[백준/실버1] 백준 28117번 prlong longf - c++ (dp)

 

문제

모든 int가 longlong으로 바뀐 문자열이 주어진다. 가능한 원래 문자열은 모두 몇 가지인가?

-> longlong을 int로 바꿀 수 있는데 만들 수 있는 문자열의 개수

문제 해설

long => A로 치환

int => B로 치환

AA -> B로 바꿀 수 있음

long의 개수	나올 수 있는 경우	경우의 수
A(1) /  0	X	1
AA (2)	AA / B	2
AAA (3)	BA / AB / AAA	3
AAAA (4)	BAA / ABA / AAB / BB / AAAA	5 (2+3)
AAAAA (5)	BAAA / ABAA / AABA / AAAB BBA / BAB / ABB / AAAAA	8 (3+5)
AAAAAA (6)	AAAAAA / BAAAA / ABAAA / AABAA /  AAABA / AAAAB / BBAA / BABA / BAAB  ABBA / ABAB / AABB / BBB	13 (5+8)
AAAAAAA (7)	AAAAAAA / BAAAAA / ABAAAA / AABAAA / AAABAA / AAAABA /  AAAAAB / BBAAA / BABAA / BAABA/ BAAAB / ABBAA / ABABA / ABAAB / AABBA / AABAB / AAABB / BBBA /  BABB / BBAB/ ABBB	21 (8+13)

 

해당 규칙을 찾아보면 

피보나치와 같은 점화식을 찾아볼 수 있다.

dp[0] = 1 / dp[1] = 1 / dp[2] =2 / dp[3] =3 / dp[4] =5

즉

dp[i] = dp[i-2] + dp[i-1]

이라는 점화식을 얻을 수 있다. 

(의심하다가 7까지 다 해봤다.)

 

예제 입력 1

15
prlonglonglongf

printlongf / printlongintf / prlonglonglongf => 3개

long의 개수 3개 => dp[3] =3 성립

 

예제 입력 2

22
longlongdoublelonglong

이때 주의해야할 게 

2+2인지 2*2인지이다.

답은 2*2이다.

 

longlonglongdoublelonglong이라는 문자열을 두고 다 만들어보면

3+2 = 5 가 아닌 3*2=6인 것을 알 수 있다.

(스스로 해보면서 익혀보자)

 

코드

#include <bits/stdc++.h>


using namespace std;

int main (){
    ios_base::sync_with_stdio(false); 
    cin.tie(nullptr); cout.tie(nullptr);
    int n;
    cin >>n;
    int dp[21]={0,};
    dp[0]=1;
    dp[1]=1;
    dp[2]=2; //i는 long의 개수 
    dp[3]=3;
    for(int i=4; i<=20; i++){ // n 이 80까지니까 80/4해서 최대 20개밖에 안됨
    dp[i]= dp[i-1]+dp[i-2];
    }
    
    int result =1;
    string s="";
    cin >> s;
    s+='k'; //아무거나 덧붙여서 마지막꺼 넣을 수 있도록
    int cnt=0; //long의개수
    for(int i=0; i<n+1; i++){
        if(i+3<=n&&s[i]=='l'&&s[i+1]=='o'&&s[i+2]=='n'&&s[i+3]=='g'){
            cnt++;
            i+=3;
        }
        else{
            result*=dp[cnt];
            cnt=0;
        }
    }
    
    cout << result;
    
    return 0; 
}

 

dp[] => 연속된 long의 개수에 따른 생성할 수 있는 문자열의 수

연속되는 long의 개수 -> cnt 

result 는 만들 수 있는 문자열의 개수 -> 연속되는 long의 개수로 나온 값들을 곱해줘야함 (예 ) 2*3)

long 문자를 찾음 -> 있음 -> cnt++ -> i+3

                          -> 없음 -> cnt 초기화(연속이 끊겨서) -> dp[cnt]의 값 넣어줌

 

이렇게 문제를 해결할 수 있다.