백준: Class 5 - 9466, 10942(manachers 알고리즘), 11049

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

9466: 텀 프로젝트

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

    while( t-- ){
        int n;
        cin >> n;
        for(int i = 1; i <= n; i++){
            ind[i] = 0;
        }
        for(int i = 1; i <= n; i++){
            cin >> nums[i];
            ind[nums[i]]++;
        }
        int ans = 0;
        queue<int> q;
        for(int i = 1; i <= n; i++){
            if( ind[i] == 0 ){
                q.push(i);
                ans++;
            }
        }
        while( q.size() ){
            int now = q.front();
            q.pop();
            int nx = nums[now];
            ind[nx]--;
            if( ind[nx] == 0 ){
                q.push(nx);
                ans++;
            }
        }
        cout << ans << '\n';
    }

위상 정렬 문제다
연결된 게 하나 밖에 없어서 그냥 배열로 했다
ind 배열에 연결된 것들의 수를 저장한다. 만약 연결된 것들이 없으면 큐에 넣는다.
큐가 빌 때까지, 큐 안의 것과 연결된 애가 걔를 제외하고 연결된 것들이 없다면 얘도 큐에 넣어준다.

ex) 백준 예제
1
7
3 1 3 7 3 4 6


     1 2 3 4 5 6 7
ind: 1 0 3 1 0 1 1

queue <2, 5>
2에 연결된 1 -> ind가 0이 되므로 queue에 push
     1 2 3 4 5 6 7
ind: 0 0 3 1 0 1 1

queue <5, 1>
5에 연결된 3 -> ind가 2가 되므로 넘어감
     1 2 3 4 5 6 7
ind: 0 0 2 1 0 1 1

queue <1>
1에 연결된 3 -> ind가 1이 되므로 넘어감
     1 2 3 4 5 6 7
ind: 0 0 1 1 0 1 1
팀을 이룬 애들만 ind가 남음

</br>

10942: 팰린드롬?

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

int nums[4001];
int manachers[4001];

int func(int a, int b){
    int aa = 2*(a-1) + 1;
    int bb = 2*(b-1) + 1;
    int mid = (aa + bb) / 2;
    if( manachers[mid] >= (bb-aa)/2 ) return 1;
    return 0;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    cin >> n;
    nums[0] = -1;
    int ind = 1;
    for(int i = 0; i < n; i++){
        cin >> nums[ind++];
        nums[ind++] = -1;
    }

    for(int i = 0; i < ind; i++){
        int cnt = 0;
        for(int j = 1; j < ind; j++){
            if( i-j < 0 || ind <= i+j || nums[i-j] != nums[i+j] ){
                break;
            }
            cnt++;
        }
        manachers[i] = cnt;
    }

    int t;
    cin >> t;
    while( t-- ){
        int a, b;
        cin >> a >> b;
        cout << func(a, b) << '\n';
    }
}

오늘 어쩌다 manachers 알고리즘을 봤었는데 어째 이 문제 보니까 바로 써먹게 생각나더라ㅋㅋ
간단하니 대충 설명하자면

s  = abcbdd
s' = 0a0b0c0b0d0d0

manachers[i] = i를 중심으로 반지름이 몇까지 갈 수 있는가?
ex) (0a0 - 010), (0a0b0a0 - 0103010), (0d0d0 - 01210)

따라서
s': 0a0b0c0b0d0d0
ma: 0101030101210

만약 1부터 5까지를 확인하라 하면, 그걸 manachers의 인덱스로 변환한다(2*(i-1) + 1).
따라서 (1, 9)의 중앙인 5의 가능한 반지름을 확인하면 된다.
manachers[5]가 (1, 9)의 반지름인 (9-1)/2 = 4보다 같거나 크다면 걔는 팰린드롬이겠지
</br>

11049: 행렬 곱셈 순서

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

int func(int a, int b){
    if( dp[a][b] != INT_MAX ) return dp[a][b];
    if( a == b ){
        dp[a][b] = 0;
        return 0;
    }
    if( b-a == 1 ){
        dp[a][b] = r[a] * c[a] * c[b];
        return dp[a][b];
    }
    for(int i = a; i < b; i++){
        dp[a][b] = min(dp[a][b], func(a, i) + func(i+1, b) + r[a]*c[i]*c[b]);
    }
    return dp[a][b];
}

재귀 dp로 풀었다
dp[시작][끝] = min(dp[시작][끝], dp[시작][중간점] + dp[중간점][끝] + 행렬 곱 연산 수)
</br>

---

열심히 합시다
</br>