[백준] 별자리가될수있다면 - 30821번

2024. 6. 13. 13:02·여러가지/알고리즘 & 자료구조

별자리가 될 수 있다면

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
'여러가지/알고리즘 & 자료구조' 카테고리의 다른 글
  • [백준] 동전 0 - 11047번
  • Greedy 알고리즘
  • [백준] 청정순열 - 25176
  • [백준] 슈퍼마리오 - 2851번
hyeseong-dev
hyeseong-dev
안녕하세요. 백엔드 개발자 이혜성입니다.
  • hyeseong-dev
    어제 오늘 그리고 내일
    hyeseong-dev
  • 전체
    오늘
    어제
    • 분류 전체보기 (283)
      • 여러가지 (107)
        • 알고리즘 & 자료구조 (72)
        • 오류 (4)
        • 이것저것 (29)
        • 일기 (1)
      • 프레임워크 (39)
        • 자바 스프링 (39)
        • React Native (0)
      • 프로그래밍 언어 (38)
        • 파이썬 (30)
        • 자바 (3)
        • 스프링부트 (5)
      • 운영체제 (0)
      • DB (17)
        • SQL (0)
        • Redis (17)
      • 클라우드 컴퓨팅 (2)
        • 도커 (2)
        • AWS (0)
      • 스케쥴 (65)
        • 세미나 (0)
        • 수료 (0)
        • 스터디 (24)
        • 시험 (41)
      • 트러블슈팅 (1)
      • 자격증 (0)
        • 정보처리기사 (0)
      • 재태크 (5)
        • 암호화폐 (5)
        • 기타 (0)
  • 블로그 메뉴

    • 홈
    • 태그
    • 방명록
  • 링크

  • 공지사항

  • 인기 글

  • 태그

    파이썬
    mybatis
    프로그래머스
    spring
    자바
    ecs
    celery
    FastAPI
    docker
    시험
    WebFlux
    reactor
    #개발자포트폴리오 #개발자이력서 #개발자취업 #개발자취준 #코딩테스트 #항해99 #취리코 #취업리부트코스
    EC2
    DP
    Python
    SAA
    취업리부트
    Spring WebFlux
    Redis
    완전탐색
    항해99
    AWS
    백준
    Spring Boot
    RDS
    OOP
    java
    Docker-compose
    그리디
  • 최근 댓글

  • 최근 글

  • hELLO· Designed By정상우.v4.10.0
hyeseong-dev
[백준] 별자리가될수있다면 - 30821번
상단으로

티스토리툴바