[BOJ 25176] 백준 25176번 - 청정수열 (Easy)

		2022 서강대학교 청정수컵 풀이
A		[BOJ 25175] 두~~부 두부 두부
B		[BOJ 25176] 청정수열 (Easy)
C		[BOJ 25177] 서강의 역사를 찾아서
D		[BOJ 25178] 두라무리 휴지
E		[BOJ 25179] 배스킨라빈스~N~귀엽고~깜찍하게~
F		[BOJ 25180] 썸 팰린드롬
G		[BOJ 25181] Swap the elements
H		[BOJ 25182] 청정수열 (Hard)
I		[BOJ 25183] 인생은 한 방
J		[BOJ 25184] 동가수열 구하기
K		[BOJ 25185] 카드 뽑기
L		[BOJ 25186] INFP 두람
M		[BOJ 25187] 고인물이 싫어요
N		[BOJ 25188] 1, 3, 모 나누기

1. 문제

$25176$. 청정수열 (Easy) (2022 서강대학교 청정수컵 B번)

백준 25176번 - 청정수열 (Easy) (https://www.acmicpc.net/problem/25176)

2. 풀이

청정수열의 점수는 (두 개의 i 사이에 있는 수의 합) × i이므로, 두 개의 $i$ 사이에 수가 최대한 없어야, 점수를 최소로 만들 수 있다.

따라서 점수가 최소인 청정수열은 1122, 221133과 같이, $1$ 이상 $N$ 이하인 모든 $i$에 대해 두 개의 $i$가 서로 붙어있는 수열이다.

붙어있는 두 개의 수를 하나로 간주하면, $1$ 이상 $N$ 이하의 수로 만들 수 있는 모든 순열의 개수와 동일하다. 따라서 정답은 $N!$이다. 아래에 예시가 있다.

$N=3$일 때,

$112233$ $\rightarrow$ $123$ $\;\;\;$ $113322$ $\rightarrow$ $132$
$221133$ $\rightarrow$ $213$ $\;\;\;$ $223311$ $\rightarrow$ $231$
$331122$ $\rightarrow$ $312$ $\;\;\;$ $332211$ $\rightarrow$ $321$

$123$ 순열의 개수 $3!=6$

3. 채점 결과

4. 회고

.

5. 코드