백준: Class 3 ⑥ - 11403, 11659, 11723

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

11403: 경로 찾기

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

    for(int k = 0; k < n; k++){
        for(int i = 0; i < n; i++){
            for(int j = 0; j < n; j++){
                if( graph[i][j] == 0 && graph[i][k] == 1 && graph[k][j] == 1 ){
                    graph[i][j] = 1;
                }
            }
        }
    }

    for(int i = 0; i < n; i++){
        for(int j = 0; j < n; j++){
            cout << graph[i][j] << ' ';
        }
        cout << '\n';
    }

아하~ n이 100밖에 안 돼서 플로이드 워셜 그냥 쓰면 되겠네 쉬워서 좋다

</br>

11659: 구간 합 구하기 4

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

    sum[0] = p[0];
    for(int i = 1; i < n; i++){
        sum[i] = p[i] + sum[i-1];
    }

    while( m-- ){
        int a, b;
        cin >> a >> b;

        if( a == 1 ) cout << sum[b-1] << '\n';
        else cout << sum[b-1] - sum[a-2] << '\n';
    }

위 코드의 sum[]은 이전 포스트(https://cyj893.github.io/algorithm/Algorithm15_5/)의 11399: ATM에서도 조금 다르게 사용하지만 썼던 건데
a부터 b까지의 구간 합 = b까지의 합 - a까지의 합으로 구할 수 있다. 인덱스에 유의하기
</br>

11723: 집합

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

방법 1.

    while( m-- ){
        string s;
        int t;
        cin >> s;
        if( s == "add" ){
            cin >> t;
            se.insert(t);
        }
        else if( s == "remove" ){
            cin >> t;
            if( se.count(t) ) se.erase(t);
        }
        else if( s == "check" ){
            cin >> t;
            if( se.count(t) ) cout << "1\n";
            else cout << "0\n";
        }
        else if( s == "toggle" ){
            cin >> t;
            if( se.count(t) ) se.erase(t);
            else se.insert(t);
        }
        else if( s == "all" ){
            se = allset;
        }
        else if( s == "empty" ){
            set<int> se2;
            se = se2;
        }
    }

짱 쉬운데 시간 초과가 날 수도 있다 헉

        else if( s == "all" ){
            set<int> se2;
            for(int i = 1; i <= 20; i++){
                se2.insert(i);
            }
            se.swap(se2);
        }

처음에 all을 이렇게 맨날 만들어 줬더니 시간초과 나더라
</br>

20 제한인 게 비트마스크로도 풀라고 있는 것 같아서 그렇게 풀어 보자

방법 2.

    int se = 0;
    int allset = 0;
    for(int i = 0; i < 20; i++){
        allset |= (1 << i);
    }
    for(int i = 1; i <= 20; i++){
        bitmask[i] = (1 << (i-1));
    }

    int m;
    cin >> m;

    while( m-- ){
        string s;
        int t;
        cin >> s;
        if( s == "add" ){
            cin >> t;
            se |= t;
        }
        else if( s == "remove" ){
            cin >> t;
            if( (se & bitmask[t]) == bitmask[t] ) se -= bitmask[t];
        }
        else if( s == "check" ){
            cin >> t;
            if( (se & bitmask[t]) == bitmask[t] ) cout << "1\n";
            else cout << "0\n";
        }
        else if( s == "toggle" ){
            cin >> t;
            if( (se & bitmask[t]) == bitmask[t] ) se -= bitmask[t];
            else se |= bitmask[t];
        }
        else if( s == "all" ){
            se = allset;
        }
        else if( s == "empty" ){
            se = 0;
        }
    }

allset은 111...11로 1이 20개인 상태, empty는 그냥 0으로 바꿔 주면 된다
bitmask 배열에 1, 10, 100, 1000, ...을 미리 저장해 둬서 반복 계산을 피했다.
</br>

비트마스크 쪽이 조금 더 빠르고 메모리가 적게 든다!!
</br>

---

다양하게 풀어보자
</br>