Woeful Permutation 링크
(2022.10.19 기준 Difficulty *800)
(Never cheat)

문제

lcm(1, p1) + lcm(2, p2) + ... + lcm(n, pn)이 최대가 되도록 길이 n의 임의의 순열 p를 출력

알고리즘

최소공배수와 곱셈의 성질을 잘 이용해야 한다.

풀이

일단 나는 이 문제를 직감적으로 풀었고, 정확한 타당성 증명은 못한다.

1 차이가 나는 두 양수끼리는 공약수가 1 제외하고는 없다. 그러면 1 차이가 나게끔 두 양수를 묶으면 최소공배수가 최대가 될 것이다.

그리고 곱셈은 덧셈보다 훨씬 더 크게 폭이 크다(?)
만약 1 ~ 10까지의 순열이 있다고 생각해보자.
1 * 2 + 3 * 4 + 5 * 6 + 7 * 8 + 9 * 10 = 190
1 * 10 + 2 * 9 + 3 * 8 + 4 * 7 + 5 * 6 = 110
큰 수끼리 묶어서 곱을 하여 합을 구하는게 훨씬 더 커진다.

위 두 성질을 같이 생각한다면
1 ~ n까지의 순열이 있다면
뒤에서부터 n은 n-1, n-1은 n끼리 묶으면서 앞까지 오면 된다.
그러면 1 차이가 나는 두 양수끼리 묶으니깐 최소공배수는 두 수의 곱이 되고, 최대한 큰 수끼리 묶으니깐 곱의 합이 최대로 커질 것이다.

코드

import sys; input = sys.stdin.readline

# 1 차이가 나게끔 두 양수끼리 묶어서 출력
# 개수가 홀수일 경우엔 1은 1이랑 묶으면 된다.
for _ in range(int(input())):
    n = int(input())
    if n % 2: # 홀수
        print(1, end = ' ') # 1부터 출력
        for i in range(3, n + 1, 2): # i, i + 1은
            print(i, i - 1, end = ' ') # i + 1, i랑 묶이게 출력
        print()
    else: # 짝수
        for i in range(2, n + 1, 2): # i, i + 1은
            print(i, i - 1, end = ' ') # i + 1, i랑 묶이게 출력
        print()

여담

정말 빠르게 풀었던 것 같다.
동물적 감각이 확 왔던 것 같다. 뿌듯