백준: Class 5 - 1509, 10844, 1562

</br> 클래스 5 계속
</br>

1509: 팰린드롬 분할

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

    string s = "#";
    for(int i = 0; i < t.size(); i++){
        s.append(1, t[i]);
        s.append(1, '#');
    }
    for(int i = 0; i < s.size(); i++){
        int cnt = 0;
        for(int j = 1; j < s.size(); j++){
            if( i-j < 0 || s.size() <= i+j ) break;
            if( s[i-j] != s[i+j] ) break;
            cnt++;
        }
        manachers[i] = cnt;
    }

    dp[1] = 1;
    for(int i = 3; i < s.size(); i+=2){
        dp[i] = s.size();
        for(int j = 1; j <= i; j+=2){
            if( manachers[(i+j)/2] >= (i-j)/2 ){
                dp[i] = min(dp[i], dp[j-2]+1);
            }
        }
    }

    cout << dp[s.size()-2] << endl;

이번에도 마나커 알고리즘을 썼다
dp[i] = i까지의 최소 그룹 수로, 만약 j~i가 팰린드롬이면 한 그룹으로 묶이기 때문에 j이전까지의 최소 더하기 1을 하면 된다. 따라서 dp[i] = min(dp[i], dp[j-2] + 1)

ex) 백준 예제
BBCDDECAECBDABADDCEBACCCBDCAABDBADD
#B#B#C#D#D#E#C#A#E#C#B#D#A#B#A#D#D#C#E#B#A#C#C#C#B#D#C#A#A#B#D#B#A#D#D#
01210101210101010101010101050101210101010101232101010101210105010101210

1, 3, 5, ... s.size()-2의 dp를 만들면 된다.

B
1

BB
11

BBC
112

BBCD
1123

BBCDD
11233

...

대충 이런 느낌의 dp
</br>

그리고 1562: 계단 수를 풀려고 했는데, 잘 안 풀리더라
근데 걔의 쉬운 버전이 있대서 그걸 먼저 풀어보기로 했다

10844: 쉬운 계단 수

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

    dp[1][0] = 0;
    for(int i = 1; i <= 9; i++){
        dp[1][i] = 1;
    }
    for(int i = 2; i <= n; i++){
        dp[i][0] = dp[i-1][1];
        for(int j = 1; j <= 8; j++){
            dp[i][j] = dp[i-1][j-1] + dp[i-1][j+1];
            dp[i][j] %= 1000000000;
        }
        dp[i][9] = dp[i-1][8];
    }

    int ans = 0;
    for(int i = 0; i <= 9; i++){
        ans += dp[n][i];
        ans %= 1000000000;
    }
    cout << ans << endl;

얘는 원본에 비해 정말 쉬운 애다
dp[i][j] = i번째, 끝자리 숫자가 j인 계단수들의 개수로 만들었다.
0, 1, 8, 9일 때를 잘 처리해 주면 된다.

abc...0일 경우 abc...01로 확장
abc...1일 경우 abc...10, abc...12로 확장
...
abc...8일 경우 abc...87, abc...89로 확장
abc...9일 경우 abc...98로 확장

따라서
dp[i][0]은 dp[i-1][1]의 개수와 같고,
나머지 1~8은 dp[i][j] = dp[i-1][j-1] + dp[i-1][j+1]
dp[i][9]는 dp[i-1][8]

</br>

그럼 이제 그냥 계단 수를 풀어 보자

1562: 계단 수

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

    for(int i = 1; i <= n; i++){
        for(int j = 0; j <= 9; j++){
            for(int k = 1; k <= 1023; k++){
                dp[i][j][k] = 0;
            }
        }
    }
    for(int i = 1; i <= 9; i++){
        dp[1][i][1<<i] = 1;
    }
    for(int i = 2; i <= n; i++){
        for(int j = 1; j <= 1023; j++){
            dp[i][0][j|1] += dp[i-1][1][j];
            dp[i][0][j|1] %= 1000000000;
            for(int k = 1; k <= 8; k++){
                dp[i][k][j|(1<<k)] += dp[i-1][k-1][j] + dp[i-1][k+1][j];
                dp[i][k][j|(1<<k)] %= 1000000000;
            }
            dp[i][9][j|(1<<9)] += dp[i-1][8][j];
            dp[i][9][j|(1<<9)] %= 1000000000;
        }

    }
    int ans = 0;
    for(int i = 0; i <= 9; i++){
        ans += dp[n][i][1023];
        ans %= 1000000000;
    }
    cout << ans << endl;

위에 애를 응용하면 된다
이번엔 int dp[101][10][1024];로 사용한다. 여기서 마지막 1024는 0~9의 set을 의미한다.

ex) 0, 1, 5를 포함했다면 1 | 10 | 10000 = 10011 = 35

따라서, dp[i-1][k-1][j]가 있다면 dp[i][k][j|(1<<k)]에 더해준다. 현재 set 상태인 j에 숫자 k가 더해졌으므로~~
</br>

---

쉬운 계단 수도 바로 풀리고 1562: 계단 수도 쉬운 계단 수를 보고 나니 바로 방법을 알아서 풀리는데 처음에 그냥 1562 계단 수만 봤을 때는 안 풀렸다
열심히 하자
</br>