[Algorithm] Connecting Towns

> Quest.

Gandalf is travelling from Rohan to Rivendell to meet Frodo but there is no direct route from Rohan (T1) to Rivendell (Tn).

But there are towns T2,T3,T4...Tn-1 such that there are N1 routes from Town T1 to T2, and in general, Ni routes from Ti to Ti+1 for i=1 to n-1 and 0 routes for any other Ti to Tj for j ≠ i+1

Find the total number of routes Gandalf can take to reach Rivendell from Rohan.

> Input.

Input Format 

The first line contains an integer T, T test-cases follow. 

Each test-case has 2 lines. The first line contains an integer N (the number of towns). 

The second line contains N - 1 space separated integers where the ith integer denotes the number of routes, Ni, from the town Ti to Ti+1

> Output.

Output Format 

Total number of routes from T1 to Tn modulo 1234567 

> solve

단순하게 요약하면 1) 목적지까지 주어진 마을을 가장 빨리 지나올때, 가능한 방법의 수를 구하는 것입니다. 그러나 !!! modulo 가 걸려있지요.

modulo 는 쉽게 순환하는 것이라고 생각할 수 있어요.

12시가 넘으면 다시 1시로 돌아오듯 순환하는 숫자로 작성하라는 이야기이죠.

#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>

int main() {
    int T, N, Ni;
    scanf("%d", &T);
    
    for(int i=0; i<T; i++){
        scanf("%d", &N);
        long int sum = 1;
        for(int j=0; j<N-1; j++){
            scanf("%d", &Ni);
            sum = ( sum*Ni > 1234567 ? sum*Ni % 1234567 : sum*Ni );
        }
        printf("%ld\n",sum);
    }
    return 0;
}

문제 출처 : https://www.hackerrank.com/challenges/connecting-towns