백준: Class 4 - 9935, 10830, 14938

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

9935: 문자열 폭발

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

방법 1.

    while( 1 ){
        bool explode = false;
        queue<char> t;
        while( q.size() ){
            char c = q.front();
            q.pop();
            if( c == bomb[0] ){
                int i = 1;
                queue<char> b;
                b.push(c);
                for( ; i < bomb.size(); i++){
                    char c = q.front();
                    if( c != bomb[i] ) break;
                    q.pop();
                    b.push(c);
                }
                if( i != bomb.size() ){
                    while( b.size() ){
                        t.push(b.front());
                        b.pop();
                    }
                }
                else explode = true;
            }
            else t.push(c);
        }
        q = t;
        if( !explode ) break;
    }

    if( q.size() ){
        while( q.size() ){
            cout << q.front();
            q.pop();
        }
        cout << '\n';
    }
    else cout << "FRULA\n";

큐로 삭제해 주면서 풀었다.
시간 초과 난다 당연하네
</br>

방법 2.

    int now = 0;
    for(int i = 0; i < s.size(); i++){
        ans[now] = s[i];
        if( s[i] == bomb[bomb.size()-1] ){
            int j = 1;
            for( ; j < bomb.size(); j++){
                if( ans[now-j] != bomb[bomb.size()-1-j] ) break;
            }
            if( j == bomb.size() ) now -= bomb.size();
        }
        now++;
    }
    if( now ){
        for(int i = 0; i < now; i++){
            cout << ans[i];
        }
        cout << '\n';
    }
    else cout << "FRULA\n";

힌트를 봐 버렸다
요지는 O(N)에 풀기 위한다는 것
일단 답 배열에 문자열을 계속 넣는다.
만약 폭탄의 마지막을 발견했다면, 답 배열을 끝에서부터 폭탄을 포함했는지 탐색한다.
만약 폭탄이 있다면, 답 배열의 인덱스를 폭탄 크기만큼 앞으로 당겨 뒤에 덮어 쓰도록 한다.
폭탄이 없다면 그냥 계속 문자열을 더하면 된다
</br>

10830: 행렬 제곱

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

int mat[6][6];
int a[6][6];
int t[6][6];
long long n, b;

int* func(int* m1, int* m2){
    for(int i = 0; i < n; i++){
        for(int j = 0; j < n; j++){
            t[i][j] = 0;
            for(int k = 0; k < n; k++){
                t[i][j] += (*(m1+i*6+k)) * (*(m2+k*6+j));
                t[i][j] %= 1000;
            }
        }
    }
    swap(t, mat);
    return (int*)mat;
}

int* func2(long long d){
    if( d == 1 ) return (int*)a;
    if( d % 2 == 0 ){
        int* p = func2(d/2);
        return func(p, p);
    }
    int* p = func2(d-1);
    return func((int*)a, p);
}

// in main()
    int* p = func2(b);
    for(int i = 0; i < n; i++){
        for(int j = 0; j < n; j++){
            cout << *(p+i*6+ j)%1000 << ' ';
        }
        cout<<endl;
    }

왜 계속 틀려… 뭐야 했는데 b의 범위가 애초에 long long으로 받아야 합니다 주의

아무튼 얘는 저번에 제곱 문제(13172: Σ, https://cyj893.github.io/algorithm/Algorithm16_8/)와 똑같다 그냥 행렬로 바뀜
오랜만에 막 이차원 배열을 리턴하고 받아서 처리하고 하려니까 좀 헷갈린다ㅋㅋ

func()에서 마지막에 swap(t, mat);을 해주지 않으면 막 t에다 t를 곱하고 난리가 날 수 있으니 꼭 새 주소를 변환해 주세요 뻘짓 좀 함
</br>

14938: 서강그라운드

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

    for(int k = 1; k <= n; k++){
        for(int i = 1; i <= n; i++){
            for(int j = 1; j <= n; j++){
                graph[i][j] = min(graph[i][j], graph[i][k]+graph[k][j]);
            }
        }
    }
    int ans = 0;
    for(int i = 1; i <= n; i++){
        int item = 0;
        for(int j = 1; j <= n; j++){
            if( graph[i][j] <= m ) item += t[j];
        }
        ans = max(ans, item);
    }
    cout << ans << endl;

간만에 플로이드 워셜 문제
m 이하의 거리면 방문 가능하다!! 실수로 graph[i][j] < m해서 틀렸다
</br>

---

클래스 4도 얼마 안 남았다
</br>