1주차 | 문제 1. 경로의 개수
문제
구름이가 사는 구름 나라는 n개의 섬으로 이루어져 있습니다. 섬은 1번부터 n까지 번호가 매겨져 있습니다. 구름 나라는 사람들이 섬들 사이를 편하게 이동할 수 있도록 섬과 섬 사이에 많은 다리를 설치했습니다.
설치된 다리들은 아래의 특징들을 만족합니다.
- i번 섬에 연결된 모든 다리는 i+1번 섬과 연결되어 있습니다. 단, n번 섬은 1번 섬으로 연결됩니다.
- 다리는 단방향으로, 돌아올 수는 없습니다.
- i번 섬은 항상 i+1섬으로 가는 다리는 여러 개 일 수 있습니다.
섬의 개수와 각 섬에서 건설된 다리의 개수가 주어졌을 때, 구름이는 1번 섬에서 정확히 n개의 다리를 사용하여 다시 1번 섬으로 돌아올 때 경로의 경우의 수를 구하고자 합니다.
i번 섬에서 i+1번 섬을 방문할 때, 다른 다리를 이용했다면 다른 경로로 봅니다. 조건에 따라서 경로의 경우의 수를 찾는 프로그램을 작성하시오.
입력
첫째 줄에 섬의 개수 정수 n(2≤n≤10)이 주어집니다.둘째 줄에 각 섬에 건설된 다리의 개수가 공백을 두고 주어집니다.
i번째 수는 i번 섬의 다리의 개수입니다. 한 섬에 설치되어 있는 다리의 개수는 1 이상 100 이하의 정수입니다.
출력
1번 섬에서 출발하여, 다시 1번 섬으로 돌아오는 경로의 경우의 수를 구하시오.
풀이
n=int(input()) # 섬의 개수
n_list=list(map(int,input().split())) # 각 섬의 다리의 개수(공백으로 구분)
case=1
for i in n_list:
case*=i # 각 섬의 다리의 개수를 모두 곱해줌
print(case)그림을 그려 문제를 이해해보면 확률과 통계에서 배웠던 경우의 수를 구하는 문제임을 알 수 있다.
각 섬의 다리의 개수를 순서대로 곱해주면 경우의 수를 구할 수 있다.
보통 누적 합을 구할 때는 초기값을 0으로 설정하지만, 이 경우에는 곱셈을 하기 위해 case의 초기값을 1로 설정해주었다.
반응형