청정수열 (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);
}
}
'여러가지 > 알고리즘 & 자료구조' 카테고리의 다른 글
Greedy 알고리즘 (1) | 2024.06.14 |
---|---|
[백준] 별자리가될수있다면 - 30821번 (0) | 2024.06.13 |
[백준] 슈퍼마리오 - 2851번 (0) | 2024.06.13 |
[백준] 암호 만들기 - 1759번 (0) | 2024.06.13 |
[백준] 단어나누기 - 1251번 (0) | 2024.06.12 |