선의 수 구하기/complete_graph(선의 수 구하기 알고리즘)

20151024

*이문제는 dovelet 에 있는 알고리즘 문제입니다.

선의 수 구하기/complete_graph 

프로그램 명: complete_graph     

프로그램 명: complete_graph

제한시간: 1 초

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

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

입력

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

출력

선의 수를 출력한다.

입출력 예

입력

4

출력

6

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

문제 풀이

1) 풀이

import java.io.PrintStream;
import java.util.Scanner;

public class Main {
 
	Scanner sc = new Scanner(System.in);
	static PrintStream p = System.out;
	int n;
	
	public static void main(String[] args) {
		Main m = new Main();
		m.input();
		m.Output();
	}
	void input(){
		n = sc.nextInt();
	}
	 void Output(){
		 // 이러한 수식으로도 구할 수 있습니다.  n*(n-1)/2;
		 int sum = 0;
		 int m = n-1;
		 for(int a = 0; a < n-1; a++){
			 sum = sum + m;
			 m = m-1;
		 }
		 p.println(sum);
	 }  
}

*짧게 코딩하는것도 좋지만 저는 함수와 객체 지향개념을 쓰고 싶어서 이렇게 코딩 했습니다.

일정 비율로 선의 개수가 늘어가고 그 규칙을 찾아 수식으로 풀면 되는 문제 입니다.

저는 ..수식을 못 찾고 한 꼭지점부터 그어지는 선의 개수가 n-1 개에서 -1 씩 차감 하면서

1까지 생기는점을 가지고 문제를 풀었습니다.

n*(n-1)/2 이런 수식을 찾는게 더 정석 같은 풀이 같습니다.