문제 정의
변수 num이 주어졌을 때, 1부터 num까지의 숫자를 사용해 만들 수 있는 순열 중에서 처음에는 감소하다가 이후에는 증가하는 순열의 개수를 구하는 것이 목표입니다. 예를 들어 num=3이라면 사용할 수 있는 숫자는 1, 2, 3이고, 조건을 만족하는 순열은 [3, 1, 2]와 [2, 1, 3] 두 가지이므로 정답은 2가 됩니다.
핵심 아이디어: 숫자 1의 위치
모든 순열에서 감소가 증가로 바뀌는 전환점은 최솟값인 1의 위치에 의해 결정됩니다. 1 다음에 오는 숫자들은 항상 증가하기 때문입니다. 따라서 순열이 '감소 후 증가' 형태가 되려면 1은 2번째 위치부터 num-1번째 위치 사이에 있어야 합니다. ([ → …1… → ])
반대로 1이 맨 앞에 있으면 수열 전체가 증가하고([ 1.. → ]), 맨 끝에 있으면 수열 전체가 감소합니다([ … → 1 ]). 이 두 경우는 우리가 찾는 조건에 해당하지 않습니다.
조합 공식 유도
num=4인 경우를 단계별로 살펴보겠습니다.
1을 2번째 위치에 배치: [-, 1, -, -] 첫 번째 위치에는 나머지 숫자 (2, 3, 4) 중 하나를 자유롭게 선택할 수 있습니다. 예를 들어 2를 고르면 수열은 [2, 1, 3, 4]가 되며, 이 경우 가능한 순열은 3C1개입니다.
1을 3번째 위치에 배치: [-, -, 1, -] 첫 번째와 두 번째 위치에는 세 숫자 (2, 3, 4) 중 두 개를 골라 배치해야 하므로, 총 순열 수는 3C2개입니다.
따라서 num=4일 때 총 순열의 개수는 3C1 + 3C2 = 3 + 3 = 6입니다.
일반화하면, 임의의 num=x에 대해 개수는 x-1C1 + x-1C2 + … + x-1Cx-2이며, 이항정리에 의해 2x-1 − 2로 간단히 계산할 수 있습니다.
예제 입력 및 출력
입력 — num = 4
출력 — 감소 후 증가하는 순열의 개수: 6
설명 — 조건을 만족하는 순열은 다음과 같습니다.
[ 2, 1, 3, 4 ], [ 3, 1, 2, 4 ], [ 4, 1, 2, 3 ] → 1이 2번째 위치 [ 2, 3, 1, 4 ], [ 2, 4, 1, 3 ], [ 3, 4, 1, 2 ] → 1이 3번째 위치
입력 — num = 6
출력 — 감소 후 증가하는 순열의 개수: 30
설명 — 가능한 순열 중 일부는 다음과 같습니다.
[ 2, 1, 3, 4, 5, 6 ], [ 3, 1, 2, 4, 5, 6 ], [ 4, 1, 2, 3, 5, 6 ], [ 5, 1, 2, 3, 4, 6 ], [ 6, 1, 2, 3, 4, 5 ], …, [ 6, 5, 4, 3, 1, 2 ]
구현 접근 방법
이 접근 방식에서는 위에서 유도한 공식을 이항정리를 통해 직접 계산합니다. 또한 i의 num 제곱을 반환하는 함수 value(long long i, long long num)를 함께 작성합니다.
- 변수 num을 입력으로 받습니다.
- 함수 permutations_increase_decrease(int num)는 num을 인자로 받아 1부터 num까지의 숫자로 만든 순열 중 감소 후 증가하는 순열의 개수를 반환합니다.
- 함수 value(long long i, long long num)는 (inum) % temp를 계산합니다. 여기서 temp = 1000000007입니다.
- permutations_increase_decrease(int num) 내부에서 temp = 1000000007로 설정합니다.
- num이 1이면 가능한 순열이 없으므로 0을 반환합니다.
- 그렇지 않으면 공식을 이용해 count = (value(2, num - 1) - 2) % temp로 설정합니다.
- count를 결과로 반환합니다.
예제 코드
#include <bits/stdc++.h>
using namespace std;
long long value(long long i, long long num){
int temp = 1000000007;
if (num == 0){
return 1;
}
long long j = value(i, num / 2) % temp;
j = (j * j) % temp;
if(num & 1){
j = (j * i) % temp;
}
return j;
}
int permutations_increase_decrease(int num){
int temp = 1000000007;
if (num == 1){
return 0;
}
int count = (value(2, num - 1) - 2) % temp;
return count;
}
int main(){
int num = 4;
cout<<"감소 후 증가하는 순열의 개수: "<<permutations_increase_decrease(num);
return 0;
}출력 결과
위 코드를 실행하면 다음과 같은 출력이 생성됩니다.
감소 후 증가하는 순열의 개수: 6