[백준] 청정순열 - 25176

청정수열 (Easy)

1 초

1024 MB

989

813

760

85.586%

문제

청정수열은 길이가 2𝑁이고 1부터 𝑁까지의 정수들이 정확히 두 번씩 등장하는 수열이다.

청정수열의 점수는 1이상 𝑁이하인 모든 정수 𝑖에 대해 다음 값의 합이다.

• (두 개의 𝑖 사이에 있는 수의 합) × 𝑖

이때, "사이"는 양 끝의 𝑖를 포함한다.

길이가 2𝑁이면서 점수가 최소인 청정수열의 개수를 구해보자.

입력

첫째 줄에 정수 𝑁이 주어진다. (1≤𝑁≤10)

출력

첫째 줄에 길이가 2𝑁이면서 점수가 최소인 청정수열의 개수를 출력하라.

예제 입력 1 복사

4

예제 출력 1 복사

24

힌트

 

예시로 [3, 1, 2, 1, 3, 2]는 N이 3인 청정수열이고 이 청정수열의 점수는 다음과 같이 계산되어 50점이 된다.
 1과 1의 사이의 수들은 [1, 2, 1] 이다. 따라서 (1+2+1) × 1을 점수에 더한다.
 2와 2의 사이의 수들은 [2, 1, 3, 2] 이다. 따라서 (2+1+3+2) × 2를 점수에 더한다.
 3과 3의 사이의 수들은 [3, 1, 2, 1, 3] 이다. 따라서 (3+1+2+1+3) × 3을 점수에 더한다.
따라서 이 청정수열의 점수는 4+16+30으로 50점이다.
이 수열의 점수는 N이 3인 청정수열의 점수의 최솟값이 아니다.

 

코드 

// 메모리 : 17724
// 시간 : 208
package 청정수열;

// 시간 복잡도: O(N)
// N에 따라서 반복문이 실행되는 횟수가 결정되므로 시간 복잡도는 O(N)입니다.

import java.util.Scanner;

/*
    [핵심]
        1. 최소 순열의 개수를 구하는 것이 목적이다. 
        2. `힌트`를 보고 1 사이의 값, 2사이의 값, 3사이의 값, 4사이의 값....을 구하는 순간 낚이는거
        3. 예를들어 {1,1,2,2,3,3}이 최소 순열이다. 
            - 편의상 112233으로 포맷팅하겠다. 
            - 113322
            - 221133
            - 223311
            - 331122
            - 332211
            -> 총 6개 -> 3! -> 3 * 2 * 1이다. 
 */
public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        scanner.close();

        int factorial = 1; // 팩토리얼 값을 저장할 변수를 초기화하고 1로 설정

        // 1부터 N까지의 모든 정수를 곱하여 factorial 변수에 저장
        for (int i = 1; i <= n; i++) {
            factorial *= i;
        }

        // 최종적으로 계산된 factorial 값을 출력
        System.out.println(factorial);
    }
}