백준: Class 5 - 16566, 12850(인접행렬 경우의 수)

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

16566: 카드 게임

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

#include <bits/stdc++.h>

using namespace std;

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

    vector<int> nums, chk;
    int n, m, k;
    cin >> n >> m >> k;
    nums.assign(m, 0);
    chk.assign(m, 0);
    for(int i = 0; i < m; i++){
        cin >> nums[i];
    }
    sort(nums.begin(), nums.end());
    for(int i = 0; i < k; i++){
        int a;
        cin >> a;
        int b = upper_bound(nums.begin(), nums.end(), a) - nums.begin();
        while( chk[b] ) b++;
        cout << nums[b] << '\n';
        chk[b] = 1;
    }
}

처음에 set으로 upper_bound를 썼는데 틀렸다. set이 엄청 느리다고 한다…
그래서 그냥 벡터를 정렬해서 이분탐색 했다.
그리고 이미 사용했으면 사용 안 한 애가 나올 때까지 인덱스를 늘렸다
이러니까 의외로 시간 초과 안 나네ㅋㅋ
</br>

12850: 본대 산책2

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

#include <bits/stdc++.h>
#define MOD 1000000007

using namespace std;

vector< vector<long long> > graph;
/*
1 전산관
2 미래관
3 신양관
4 한경직기념관
5 진리관
6 학생회관
7 형남공학관
*/

vector< vector<long long> > mul(vector< vector<long long> > p1, vector< vector<long long> > p2){
    vector< vector<long long> > t;
    t.assign(8, {});
    for(int i = 0; i < 8; i++){
        t[i].assign(8, 0);
    }
    for(int i = 0; i < 8; i++){
        for(int j = 0; j < 8; j++){
            for(int k = 0; k < 8; k++){
                t[i][j] += p1[i][k] * p2[k][j];
                t[i][j] %= MOD;
            }
        }
    }
    return t;
}

vector< vector<long long> > mypow(vector< vector<long long> > p, int b){
    if( b == 1 ) return p;
    if( b % 2 == 1 ){
        return mul(p, mypow(p, b-1));
    }
    vector< vector<long long> > t = mypow(p, b/2);
    return mul(t, t);
}

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

    int d;
    cin >> d;

    if( d < 0 ) return 0;

    graph.assign(8, {});
    for(int i = 0; i < 8; i++){
        graph[i].assign(8, 0);
    }
    graph[0][1] = 1; graph[1][0] = 1;
    graph[0][2] = 1; graph[2][0] = 1;
    graph[1][2] = 1; graph[2][1] = 1;
    graph[1][3] = 1; graph[3][1] = 1;
    graph[2][3] = 1; graph[3][2] = 1;
    graph[2][4] = 1; graph[4][2] = 1;
    graph[3][4] = 1; graph[4][3] = 1;
    graph[3][5] = 1; graph[5][3] = 1;
    graph[4][5] = 1; graph[5][4] = 1;
    graph[4][7] = 1; graph[7][4] = 1;
    graph[5][6] = 1; graph[6][5] = 1;
    graph[6][7] = 1; graph[7][6] = 1;

    graph = mypow(graph, d);

    cout << graph[0][0] << endl;

}

그래프 입력하는 게 제일 힘든 문제
그런데 새롭고 유용한 걸 알게 되었다
인접행렬과 인접행렬의 거듭제곱(https://blog.naver.com/PostView.naver?blogId=gt7461&logNo=110151975370)이라는 건데, 신기하다
즉 정리하면

인접행렬 graph[][], 각 노드 간의 거리를 1이라고 하자

graph[][]^1 = 거리 1로 갈 수 있는 곳  
graph[][]^2 = 거리 2로 갈 수 있는 곳  
...
따라서 i에서 j까지, 거리 n으로 갈 수 있는 경우의 수
  = graph[i][j]^n  

신기방기
나머지는 행렬 제곱만 빠르게 구해주면 된다.
</br>

---

재밌네
</br>