BOJ 30618 donstructive

문제 링크입니다.

구간 개수 세기

순열의 각 위치마다, 그 위치에 적힌 수와 그 위치를 포함하는 구간의 개수를 곱한 값을 전부 합하면 순열의 점수를 구할 수 있습니다. 그러니 많은 구간이 지나는 위치에 큰 수를 넣는 것이 점수를 최대화시키는 전략입니다.

길이가 $N$인 순열의 $i$번째 위치가 포함되는 구간의 개수는 구간의 왼쪽 끝이 $[1, i]$, 오른쪽 끝이 $[i, N]$에 있어야 하니 총 $i(N-i+1)$개가 됩니다.

개수 비교하기

$i = 1 \cdots N$에 대해 $i(N-i+1)$의 크기를 비교해야 합니다.

$i + (N-i+1) = N+1$로 일정하므로, 두 값의 차 $ \vert i - (N-i+1) \vert $ 가 작을 수록 둘의 곱은 커집니다. 그러니 순열의 중앙에 가까운 위치부터 차례로 큰 값을 넣어줄 수 있습니다.

이를 구현하는 한 가지 방법으로, 앞의 절반을 홀수로 오름차순으로 쭉 채우고, 나머지 절반을 짝수로 내림차순으로 채우는 것으로 큰 수가 가운데로 몰리도록 만들어줄 수 있습니다.

코드

#include<bits/stdc++.h>
using namespace std;
using ll = long long;

int main(){
	cin.tie(0);cout.tie(0);ios::sync_with_stdio(false);
	int n; cin >> n;
	for(int i = 1; i <= n; i+=2) cout << i << ' ';
	for(int i = n - n%2; i; i -= 2) cout << i << ' ';
}