[BOJ 25182] 백준 25182번 - 청정수열 (Hard)

		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. 문제

$25182$. 청정수열 (Hard) (2022 서강대학교 청정수컵 H번)

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

2. 풀이

점수가 최대인 대표적인 청정수열은 $2112$, $321123$와 같은 형태이다. (물론 똑같은 점수를 가지면서 이와 같은 형태가 아닌 경우도 있다. 이는 많은 형태 중 하나일 뿐이다.) 이때, 점수 값을 일반화하면,

$1\times (1\sim 1까지의 합)\times 2$ $+$ $2\times (1\sim 2까지의 합)\times 2$ $+$ $3\times (1\sim 3까지의 합)\times 2$ $+$ $…$ $+$ $N\times (1\sim N까지의 합)\times 2$

이다. 이를 정리하면 다음과 같다.

$\displaystyle\sum_{k=1}^{N}{(k \times \frac{k\times (k+1)}{2} \times 2)}$ = $\displaystyle\sum_{k=1}^{N}{(k \times k \times (k+1))}$

시그마를 풀어서 하나의 식으로 정리할 수도 있지만, 그러면 mod 계산이 복잡해지는 식이 도출된다. $N\leq 100,000$이므로, 그냥 for문으로 합을 누적시켜서 정답을 구하면 된다.

---

점수가 최대인 청정수열의 개수는 정답($N!\times N!)에 대한 명확한 근거를 스스로 찾지 못했다. 따라서 공식 해설 pdf를 참고하는 것을 추천한다.

간단하게 정리하면 아래와 같다.

$1122$, $3355$와 같이, 두 종류의 숫자가 두 개가 연속되면서 붙어있는 형태가 존재하면, 점수를 최대로 만들 수 없다.

이 형태가 만들어지지 않으려면, $1$부터 $N$까지의 숫자들을 왼쪽 $N$자리에 랜덤으로 배정하고, $1$부터 $N$까지의 숫자들을 오른쪽 $N$자리에 랜덤으로 배정하면 된다.

따라서 정답은 $N!\times N!$이 된다.

3. 채점 결과

4. 회고

점수가 최대인 청정수열의 개수는 $1$, $4$, $36$, $576$으로 숫자가 변하는 것을 확인하고, 대충 연관성을 통해 규칙을 찾아내었다. 명확한 근거 없이 유추한 정답이라서, 나만의 풀이가 없다.

5. 코드