[PYTHON] 완전그래프 선의 개수 구하기

<문제>

​

프로그램 명: complete_graph

제한시간: 1 초

꼭지점(vertex)의 수 n 이 주어질 때 임의의 점에서 다른 점으로 바로 가는 길이 존재할 때 선의 수(edge) 을 구하는 것이 문제이다.

n 이 4 이면 6 개의 선이 존재한다.

입력

n 이 주어진다. n 은 2 이상 1000 이하의 정수이다.

출력

선의 수를 출력한다.

입출력 예

입력 4 출력 6

* 이러한 그래프를 완전 그래프(complete graph)라 합니다.

​

​

<코드>

n = int(input()) sum = 0 while n != 1: n -= 1 sum += n print(sum)

n = int(input())
sum = 0
while n != 1:
    n -= 1
    sum += n

print(sum)

n 개의 점이 있다고 하면 n 번 점은 1~n-1 번 점까지, n-1 번 점은 1~ n-2 번 점 까지 ..... 4번 점은 1,2,3 번 점과 이어지고, 3번 점은 1,2번 점과, 그리고 마지막 2번 점은 1번 점과 이어지면 완전 그래프가 된다. 따라서 n 개의 점이 있을 때 선의 개수 합은 1+2+3+...+n-2+n-1 즉 1 부터 n-1 까지의 합이 된다.

​

​

1 부터 n 까지의 합은 n(n+1) / 2 이므로 아래와 같이 구할 수 도 있다.

​

n = int(input())
print(int((n-1)*n/2))

​

​

​

​

문제 출처 - http://59.23.150.58/30stair/