백준 26156: 나락도 락이다

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

26156번: 나락도 락이다

  

나락도 락이다. 부모님께 온 연락도 락이다. 오락가락?도 락? 이다.?

  

일단은 입력받은 문자열의 부분열 중 ROCK의 개수가 몇개 있는지 찾아줘야 한다는 문제이다.

 

STEP 0.

 

문자열 S의 부분열 중 "K"이 몇개 있는지 찾는다.

이를 이용해 S의 부분열 중 "CK"이 몇 개 있는지 찾을 수 있고,

이를 이용해 S의 부분열 중 "OCK"이 몇 개 있는지 찾을 수 있고,

이를 이용해 S의 부분열 중 "ROCK"이 몇 개 있는지 찾을 수 있다.

 

S를 i번째 이후 문자부터만 셌을 때 부분열 중 문자열 "K"가 몇 개 있는지는 dp[i][4]이다.

S를 i번째 이후 문자부터만 셌을 때 부분열 중 문자열 "CK"가 몇 개 있는지는 dp[i][3]이다.

S를 i번째 이후 문자부터만 셌을 때 부분열 중 문자열 "OCK"가 몇 개 있는지는 dp[i][2]이다.

S를 i번째 이후 문자부터만 셌을 때 부분열 중 문자열 "ROCK"가 몇 개 있는지는 dp[i][1]이다.

 

예를 들어, S="BLOOCK"일 때, dp[3][2]는 3번째 문자부터 셌을 때, 즉 "OOCK"의 부분열 중 "OCK"이 몇 개 있는지이므로 그 값은 2이다.

 

문자열 char x[]=".ROCK"이라고 하자.

즉, x[1]='R', x[2]='O', x[3]='C', x[4]='K'

dp[i][j]는 s[i]==x[j]일 때 dp[i+1][j]+dp[i+1][j+1]이고

s[i]!=x[j]일 때 dp[i+1][j]값과 같을 것이다.

 

S="BLOOCK"일 떄를 다시 생각해보자.

dp[3][2]를 구한다고 해보자.

s[3]==x[2]이다. ('O')

그럼 4번째 이후 문자열부터 셌을 때 부분열 중 문자열 "CK"의 개수 (dp[4][3]) + 4번째 이후 문자열부터 셌을 때 부분열 중 문자열 "OCK"의 개수 (dp[4][2]) 가

3번째 이후 문자열부터 셌을 때 부분열 중 문자열 "OCK" 개수 (dp[3][2]) 와 같다.

직접 구해보자.

그럼 4번째 이후 문자열부터 셌을 때 부분열 중 문자열 "CK"의 개수=1개

4번째 이후 문자열부터 셌을 때 부분열 중 문자열 "OCK"의 개수=1개

3번째 이후 문자열부터 셌을 때 부분열 중 문자열 "OCK" 개수=2개

 

이번엔 dp[2][2]를 구한다고 해보자.

s[2]!=x[2]이다. ('L'!='O')

그럼 2번째 이후 문자열부터 셌을 때 부분열 중 문자열 "OCK" 개수 (dp[2][2])는 3번째 이후 문자열부터 셌을 때 부분열 중 문자열 "OCK"의 개수(dp[3][2])랑 같다.

 

다만 문제는 dp[i][4]값을 구할 때다.

i번째 이후 문자열부터 셌을 때 부분열 중 "K"의 개수는 그냥 누적합 구하는 식으로 구하면 된다.

j=4인 경우를 특수 케이스로 따로 구하지 않고 그냥 dp[i][5]값들을 전부 1로 설정한 뒤 위랑 똑같은 방식으로 dp[i][4]들을 구해도 구해진다.

 

STEP 1.

 

S="BBBROCK"을 생각해보자.

dp[4][1]=1이다.

하지만 ROCK 앞에 "BBB"가 있다. 세 개의 B는 넣어도 되고 안 넣어도 된다. 즉 하나의 "ROCK"에 대해 경우의 수가 총 2^3=8가지가 나온다.

 

s[i]=='R'인 모든 i에 대해, dp[i+1][2]*(2^(i-1))의 합이 바로 출력해야 하는 답이다.

S의 모든 R에 대해 R 이후 나오는 "OCK"의 개수 (dp[i+1][2]) 곱하기 R 앞에 있는 문자들을 뺴거나 포함시키는 경우의 수( 2^(i-1) )가 바로 출력해야 하는 답이다.

 

다음은 C++로 구현한 코드다.

이번에는 4시간동안이나 삽질했는데 바로 dp배열에 값을 저장할 때 1000000007로 나눈 나머지를 저장하지 않은 게 문제였다......

typedef long long ll;
#define DIV 1000000007
char x[6] = ".ROCK";
 
int main()
{
    int n;
    char s[1000007];
    scanf("%d", &n);
    scanf("%s", s + 1);
 
    //STEP 0
 
    ll dp[10006][6] = { 0 };
    for (int i = n + 2;i > 0;i--)
        dp[i][5] = 1;
    ll ans = 0;
    for (int j = 4;j > 1;j--)
    {
        for (int i = n;i > 0;i--)
        {
            dp[i][j] = dp[i + 1][j];
            if (x[j] == s[i])
            {
                dp[i][j] += dp[i + 1][j + 1];
                dp[i][j] %= DIV; //4시간동안 삽질한 이유
            }
        }
    }
 
    //STEP 1
 
    int jj = 1;
    for (int j = 1;j == 1;j--)
    {
        for (int i = 1;i < n + 1;i++)
        {
            if ('R' == s[i])
            {
                ans += dp[i + 1][j + 1] * jj;
            }
            jj *= 2;
            ans %= DIV;
            jj %= DIV;
        }
    }
    printf("%lld", ans);
}