[C++] 1533번 길의 개수 - 수학, 분할 정복

#include <iostream>

#define LOOP(i, N) for(int i=1; i<=N; i++)
#define MAX_N 10
#define mod 1000003

using namespace std;
typedef long long ll;

int N, S, E, T; //교차점의 개수 N, 시작점의 위치 S, 끝점의 위치,
ll st[MAX_N*5+1][MAX_N*5+1], pma[MAX_N*5+1][MAX_N*5+1], ma[MAX_N*5+1][MAX_N*5+1];  //start, power_matrix, matrix

void input()
{
    cin >> N >> S >> E >> T;
    
    LOOP(i, N*5) {
        if(!((i-1)%5)) {
            LOOP(j, N) {
                int x;
                char tmp;
                cin >> tmp; x = tmp-'0';
                if(x) pma[i][5*(j-1)+x]=ma[i][5*(j-1)+x]=1;  //가중치가 0이 아니면
            }
        }
        else pma[i][i-1]=ma[i][i-1]=1;
    }
}

void multiple(ll ma1[MAX_N*5+1][MAX_N*5+1], ll ma2[MAX_N*5+1][MAX_N*5+1])  //행렬 곱
{
    ll num[MAX_N*5+1][MAX_N*5+1]={};  //행렬 곱 후 값
    LOOP(k, 5*N) {
        LOOP(i, 5*N) {
            ll x = ma1[i][k];
            
            LOOP(j, 5*N) num[i][j]=(num[i][j]+x*ma2[k][j])%mod;
        }
    }
    
    LOOP(i, 5*N) LOOP(j, 5*N) ma1[i][j]=num[i][j];
}

void power(int n)
{
    if(n==1) return;
    power(n/2);  //분할 정복
    multiple(pma, pma);
    if(n%2) multiple(pma, ma);
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    
    input();
    
    power(T);  //분할 정복
    
    cout << pma[(S-1)*5+1][(E-1)*5+1];
    
    return 0;
}

드디어 나도 플래 문제에 손을 대기 시작했다!!! 축축축!!! 솔직히 코딩 문제 풀면서 가장 우려했던 부분이 내 수학 실력이 어디까지 뒷받침될껀가? 였다.

 

알고리즘은 수학을 많이 필요로 해서 내가 가진 수학 지식으로 어디까지 커버가 가능할지 궁금했는데 그래도 플레 3까지는 아슬아슬하게 닿는 범위인 것 같다. 아마 다이아 부터는 알고리즘을 고려하기 전에 수학부터 공부해야겠지..ㅠㅠ

 

아니... 솔직히 그래프 이론에 행렬 연산이라니 이거 너무한거 아니냐구....

 

가면 갈수록 나의 C++지식 부족이 드러나고 있다. 언제 한 번 제대로 각 잡고 C++을 공부해야될 것 같다.

 

 

<알고리즘>

1. 가중치는 길이 하나인 그래프를 생각하면 된다. 1->4로 갈 때 가중치가 4라면 1 -> 4-3 -> 4-2 > 4-1 > 4 이렇게 말이다. 그후 행렬을 통해서 길의 개수를 구해내면 간단하다.
2. 행렬 곱해야하는 개수가 많기 때문에 분할 정복을 이용한 거듭제곱을 수행해야 한다.

 

<시행착오 ? 시행차고 ?>

1. 행렬 곱을 수행할 때 인간이 행렬 계산하는 방식이 아닌 뭐랄까 위에 코드처럼 구현하면 소요 시간을 대폭 줄일 수 있었다.

void multiple(ll ma1[MAX_N*5+1][MAX_N*5+1], ll ma2[MAX_N*5+1][MAX_N*5+1])  //행렬 곱
{
    ll num[MAX_N*5+1][MAX_N*5+1]={};  //행렬 곱 후 값
    LOOP(i, 5*N) LOOP(j, 5*N)
    LOOP(k, 5*N) num[i][j]=(num[i][j] + (ma1[i][k]*ma2[k][j])%mod)%mod;
    
    LOOP(i, 5*N) LOOP(j, 5*N) ma1[i][j]=num[i][j];
}

원래는 이거였는데 고치니 8ms나 줄어들었다.

 

 

<행렬 계산기>

https://matrixcalc.org/ko/

행렬 계산기

행렬 계산기다. 혹시나 결과가 잘못되면 이걸로 확인해보면 편할 것이다.

 

 

 

 

 

 

 

※현재 고등학교 등교중인 학생입니다. 이제 알고리즘을 본격적으로 공부하기 시작해서 아직 초보입니다. 혹시 제가 잘못 알고있는 점이나 더 좋은 풀이 방법이 있어 댓글에 남겨주시면 감사히 하나하나 열심히 읽어보겠습니다. 좋아요, 단순한 댓글 한마디라도 저에겐 큰 힘이 됩니다! 감사합니다