💡 PS
[BOJ] 17505 링고와 순열
date
Feb 21, 2022
slug
boj-17505
author
status
Public
tags
PS
summary
링고와 순열에 대한 풀이입니다.
type
Post
thumbnail
category
💡 PS
updatedAt
Aug 3, 2023 08:59 AM
언어
문제
풀이
아이디어 생각하는게 재미있었다.
우선 나는 N이 주어졌을 때 반전 개수의 최소값과 최대값을 생각해보았다.
최소는
1 2 3 4 5처럼 1부터 N까지 나열되어 있을 때 0이다. 최대는 5 4 3 2 1처럼 N부터 1까지 나열되어 있을 때 N*(N-1)/2이다.또 여기서 한가지 중요한 점을 관찰할 수 있다.
반전 개수가 최대가 됐을 때의 수열을 보자.
5가 첫번째 원소에 있기 때문에 4개의 반전 개수 쌍이 추가된다. 4가 두번째에 있기 때문에 3가지의 경우가 추가된다.이렇게 각 자리마다 가지고 있는 반전 개수의 쌍이
arr[i]-1개이다.5: {(5, 4) (5, 3) (5, 2) (5, 1)}
4: {(4, 3), (4, 2), (4, 1)}
3: {(3, 2), (3, 1)}
2: {(2, 1)}
1: {}
즉, 우리는 주어지는
K에 대해서 항상 만족하는 수열을 구할 수가 있다.(어차피 K는 최대값 이하만 주어짐)
go()함수를 보자. 나는 gap이란 변수를 감소해야 할 반전개수 쌍으로 보았다. arr은 반전개수가 최대일 때의 수열이다.0번째 인덱스부터
gap이 음수가 되지 않는다면 해당 인덱스로부터 얻을 수 있는 반전개수 쌍을 빼주었다.그리고 이는
tmp벡터에 저장했다. 이는 나중에 v벡터를 출력한 후 역순으로 출력한다.16번째 줄에서
v벡터에 따로 푸쉬한 이유는 조건을 만족하는 원래 arr벡터의 원소들을 따로 저장해두기 위해서이다.코드
#include <cstdio> #include <algorithm> #include <queue> using namespace std; typedef long long ll; ll n, k; vector<int> arr; void go() { ll gap = (n*(n-1)/2) - k; vector<int> v, tmp; for(int i = n; i > 0; i--) arr.push_back(i); for(int i = 0; i < arr.size(); i++) { if (gap - ll(arr[i]) + 1 < 0) { v.push_back(arr[i]); continue; } gap = gap - ll(arr[i]) + 1; tmp.push_back(arr[i]); } for(int i = 0; i < v.size(); i++) printf("%d ", v[i]); for(int i = tmp.size()-1; i >= 0; i--) printf("%d ", tmp[i]); } int main() { scanf("%lld %lld", &n, &k); go(); }