별자리가 될 수 있다면
1 초 | 1024 MB | 659 | 505 | 460 | 78.098% |
---|
문제
곧 시계는 6시, 벌써 첫 번째 별이 보인다. 정N각형 모양의 하늘에는 몇 개의 별이 뜰 수 있을까?
정N각형의 꼭짓점의 개수 N이 주어졌을 때, 정N각형의 꼭짓점을 이어 만들 수 있는 서로 다른 별의 개수를 출력하여라.
별은 정N각형의 다섯 꼭짓점에 시계 방향으로 번호를 붙였을 때, 그 꼭짓점들을 1-3-5-2-4-1 순으로 연결한 것을 의미한다. 뒤집거나 돌려서 같은 모양이 나오는 별도 정N각형의 다른 꼭짓점을 이어 만든 별이라면 서로 다른 별이다.
입력
정수 N이 주어지며, 이는 정 N각형의 꼭짓점의 개수를 나타냅니다. N의 범위는 5 이상 100 이하입니다.
출력
정𝑁각형의 꼭짓점을 이어 만들 수 있는 별의 개수를 출력한다.
예제 입력 1 복사
6
예제 출력 1 복사
6
예제 입력 2 복사
100
예제 출력 2 복사
75287520
힌트
정6각형의 꼭짓점을 이어 만들 수 있는 별은 총 6가지이다.
알고리즘 분류
코드
// 메모리 : 17652
// 시간 : 216
package 별자리가될수있다면;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt(); // n의 값 입력 받기
sc.close();
long count = calculateCombination(n, 5); // 조합 계산 (Calculate combination)
System.out.println(count);
}
// nCr 계산 메서드 (nCr calculation method)
public static long calculateCombination(int n, int r) {
// 결과 변수 초기화 (Initialize result variable)
long result = 1;
// nCr 공식: nCr = n! / ((n - r)! * r!)
// 위 공식을 두 개의 for 루프로 분해하여 계산 (Calculate the formula using two for loops)
// 1. 분자 계산 (Calculate numerator)
for (int i = 0; i < r; i++) {
// 루프 변수 i는 0부터 r-1까지 증가하며,
// 각 반복마다 n - i를 result에 곱합니다.
// 이는 n!, (n-1)!, (n-2)! ... (n-r+1)!를 계산하는 것과 동일합니다.
result *= n - i;
}
// 2. 분모 계산 (Calculate denominator)
for (int i = 1; i <= r; i++) {
// 루프 변수 i는 1부터 r까지 증가하며,
// 각 반복마다 result를 i로 나눕니다.
// 이는 r!를 계산하는 것과 동일합니다.
result /= i;
}
// nCr 값 반환 (Return nCr value)
return result;
}
}
'여러가지 > 알고리즘 & 자료구조' 카테고리의 다른 글
[백준] 동전 0 - 11047번 (0) | 2024.06.14 |
---|---|
Greedy 알고리즘 (1) | 2024.06.14 |
[백준] 청정순열 - 25176 (1) | 2024.06.13 |
[백준] 슈퍼마리오 - 2851번 (0) | 2024.06.13 |
[백준] 암호 만들기 - 1759번 (0) | 2024.06.13 |