[구름 알고리즘 먼데이 챌린지] Week1 : 1. 경로의 개수

i번째 섬에서 어떤 다리를 사용하냐에 따라 i+1번째 섬에서 사용할 수 있는 다리에 영향을 미치지 않는다.

즉, 각 섬에서 다리를 선택하는 것은 독립 사건으로 볼 수 있다.

또한, 다리는 단방향성이므로 i+1번째 섬에서 다시 i번 째 섬으로 이동하는 경우를 고려할 필요가 없으므로 독립 사건에서의 경우의 수를 구하는 문제로 판단하여 쉽게 해결할 수 있었다.

단, 10개의 섬 모두 100개의 다리가 있는 worst case의 경우 int형 범위를 벗어 날 수 있다는 것에 유의하자.

#include <iostream>
using namespace std;
int main() {
	ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	int n, num;
	long long ans =1 ;
	cin >> n;
	for(int i = 0; i < n; i++) cin >> num, ans *= num;
	cout << ans;
	return 0;
}