백준 30618번: donstructive [python]

난이도 : 실버 4
유형 : 해 구하기
출처: https://www.acmicpc.net/problem/30618

---

문제 요약

1부터 N까지로 만든 순열 중에서, 모든 연속 부분수열의 합들을 전부 더한 값을 그 순열의 점수(score) 라고 정의한다.
이 점수가 최대가 되도록 하는 순열을 하나 출력하라.

연속 부분수열의 합은 힌트에 나와있다.

---

핵심 아이디어

가운데 수가 제일 많이 쓰인다.

=> 큰 수일수록 가운데에, 작은 수일수록 양 끝에 배치하면 총합이 커진다.

홀수↑ + 짝수↓

• 앞에서부터 홀수 오름차순을 쭉 배치하고,
• 끝나면 짝수 내림차순을 뒤에 이어 붙인다.

예) N=7 → [1, 3, 5, 7, 6, 4, 2]
가운데 근처에 큰 수들이 모인다.

---

해답 및 풀이

    import sys
    input = sys.stdin.readline

    n = int(input())
    odds  = list(range(1, n + 1, 2))          # 1,3,5,...
    evens = list(range(2, n + 1, 2))[::-1]     # ...,4,2  (내림차순)
    ans = odds + evens
    print(*ans)

어떻게 하면 연속하는 배열을 만들건데 가운데에 큰 수들을 몰아서 넣을까? 의 아이디어가 핵심이었던 문제

N = 10의 경우 위 방법을 쓰면
[1,3,5,7,9,10,8,6,4,2]
이런식으로 가운데에 큰 수들을 몰아서 저장할 수 있다.