개발 블로그

문제 링크 : www.acmicpc.net/problem/1463

문제

정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지 이다.

1. X가 3으로 나누어 떨어지면, 3으로 나눈다.
2. X가 2로 나누어 떨어지면, 2로 나눈다.
3. 1을 뺀다.

정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하시오.

입력

첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다.

출력

첫째 줄에 연산을 하는 횟수의 최솟값을 출력한다.

접근 방법

dp[n] 는 n를 1로 만들기까지 필요한 연산 수이다. 

dp[n] = min(dp[n/3], dp[n/2], dp[n-1]) 로 구하는데, 이때 n이 3 또는 2로 나눠지지 않을 경우에는 최소값 후보에서 제외해야한다.

(어떤 수로 초기화해야하는가에 대한 것은 n이 최대(10^6)일 때 n에서 1을 만들기까지 필요한 연산의 최대값으로 초기화해주면 된다. 즉 10^6에서 1씩 빼는 연산으로만 1을 만들때 필요한 연산의 수인 10^6으로 초기화하면 된다. 본인은 혹시 몰라서 그것보다 더 큰수로 초기화했다.)

1부터 9까지 노가다로 구해보자.

그 다음 n=10일때를 생각해보자.

n은 3으로 나눠떨어지지 않으므로

10->5->...

10->9->...

이 두가지 경우를 생각해볼 수 있다.

dp[5] = 3이고 dp[9] = 2이므로 아래 경우로 계산했을 때 최소 연산으로 1을 만들 수 있다.

즉 dp[10] = dp[9] + 1 인 것이다. 

#include <iostream>
#include <algorithm>

using namespace std;

int X;
int ans = 1000000;

int dp[1000001] = {0};

//dp[a], dp[b], dp[c] 중 최소값 리턴
int searchMin(int a, int b, int c){
    
    int min1, min2;
    
    if(dp[a]<dp[b]) {
        min1 = dp[a];
        if(dp[a]<dp[c]) { min2 = dp[a]; }
        else min2 = dp[c];
        
    }
    else{
        min1 = dp[b];
        if(dp[b]<dp[c]) { min2 = dp[b];}
        else min2 = dp[c];
    }
    return min2;
}

int main(){
    
    int X; cin >> X;
    
    //n이 3 또는 2로 나눠지지 않을 때 최소값을 계산하는 searchMin()에서 영향을 주지 않기 위해 큰 수로 초기화한다.
    for(int i = 0; i<1000001; i++){dp[i] = 10000000;}
    
    int fir=0, sec=0, trd=0, mini=0; dp[0] = 0; dp[1] = 0;

    for(int i = 2; i<=X; i++){
        
        fir = i; sec= i; trd = i;
        
        if(i%3 == 0){
            fir = i/3;
        }
        if(i%2 == 0){
            sec = i/2;
        }
        
        trd = i-1;
        
        mini = searchMin(fir, sec, trd);
        dp[i] = mini + 1;
        
    }
    cout << dp[X];
    
    return 0;
}

문제 링크 : www.acmicpc.net/problem/1912

문제

n개의 정수로 이루어진 임의의 수열이 주어진다. 우리는 이 중 연속된 몇 개의 수를 선택해서 구할 수 있는 합 중 가장 큰 합을 구하려고 한다. 단, 수는 한 개 이상 선택해야 한다.

예를 들어서 10, -4, 3, 1, 5, 6, -35, 12, 21, -1 이라는 수열이 주어졌다고 하자. 여기서 정답은 12+21인 33이 정답이 된다.

입력

첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다.

접근 방법

처음에는 DP1[i]를 Arr[0]~Arr[i] 까지 고려했을 때 연속되는 수열의 최대 합을 저장하도록 구현했었다.즉 Arr[i-1] 부터 Arr[0] 까지 거꾸로 가면서 음수가 나오면 그 음수를 수열에 포함할 것인지 아닌지에 따라 경우를 나눠야했다.

아래 표에서 색칠한 부분을 생각해보자. 

i=6일 때, Arr[6] 이 -35로 음수이다. -35를 포함하지 않고 Arr[i] ~ Arr[5] 까지만 더한 21이 최대합을 가지는 수열이다. 이는 i=7일때도 같으며, i=8이 되는 순간 Arr[7] + Arr[8] 을 더한 33이 최대합이 된다. 

이 방법으로 구현했을 때, Arr[i]이 음수인 경우 그 음수만큼 상쇄시켜서 양수로 만들 수 있을 때 까지 Arr[i]을 거꾸로 탐색해가면서 수열에 포함해야할지 따져야 하는데 너무 복잡해져서 다시 DP2[i]를 구하는 방법으로 구현했다.

DP2[i]는 DP1[i] 과 달리 Arr[0]부터 Arr[i] 까지 고려했을 때 최대값을 담고 있지 않다. 그러나 DP2[i]를 채우면서 최대값(ans)을 따로 저장해준다면 

DP2[i]는 DP2[i-1]에다가 Arr[i] 을 계속 더해 나가는 방법이되, 더했는데도 현재 숫자인 Arr[i]보다 작으면 바로 Arr[i]이 원소 한개인 수열이 되도록 하는 것이다.  아래 예시를 들어봤다.

i = 1

10-4 vs -4 = 6

i=2

6+3 vs 3 = 9

i = 3

9+1 vs 10 = 10

i = 4

10+5 vs 5

i = 5

15+6 vs 6

i = 6

21-35 vs -35 = -14

i = 7

-14+12 vs 12 = 12

....

예시들을 아래 코드로 옮겼다.

        DP[i] = max(DP[i-1] + Arr[i], Arr[i]);
        ans = max(ans, DP[i]);

이 코드가 핵심이다. 

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int Arr[100001] = {0};
int DP[100001] = {0};

int main(){
    
    
    int N;
    cin >> N;
    int ans;
        
    for(int i = 0; i<=N; i++){ cin >> Arr[i];}
    
    DP[0] = Arr[0];
    ans = Arr[0];
    for(int i = 1; i<N; i++){
        
        DP[i] = max(DP[i-1] + Arr[i], Arr[i]);
        ans = max(ans, DP[i]);
        
    }
    
    cout << ans;
    
    
    return 0;
}

참고 : Arr[i]의 최대 값은 1000이며, N 최대값은 100,000 이다. 즉 Arr[0] ~ Arr[100,000] 에 모두 1000이 저장되어도 int 형의 범위를 넘지 않는다. 그래서 Dp[]는 int 형으로 해도 괜찮다.

문제 링크 : www.acmicpc.net/problem/1699

문제

어떤 자연수 N은 그보다 작거나 같은 제곱수들의 합으로 나타낼 수 있다. 예를 들어 11=32+12+12(3개 항)이다. 이런 표현방법은 여러 가지가 될 수 있는데, 11의 경우 11=22+22+12+12+12(5개 항)도 가능하다. 이 경우, 수학자 숌크라테스는 “11은 3개 항의 제곱수 합으로 표현할 수 있다.”라고 말한다. 또한 11은 그보다 적은 항의 제곱수 합으로 표현할 수 없으므로, 11을 그 합으로써 표현할 수 있는 제곱수 항의 최소 개수는 3이다.

주어진 자연수 N을 이렇게 제곱수들의 합으로 표현할 때에 그 항의 최소개수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 자연수 N이 주어진다. (1 ≤ N ≤ 100,000)

출력

주어진 자연수를 제곱수의 합으로 나타낼 때에 그 제곱수 항의 최소 개수를 출력한다.

접근 방법1

제곱수를 기준으로 생각했을 때, 항의 개수가 최소가 되려면 그 제곱수를 반드시 포함해야 한다고 생각했다.

예를 들어 18을 제곱수로 나타낸다고 하면, 

16<18<25 이기 때문에 18을 나타내려면 무조건 16이 들어가야한다고 생각했다.

그런데 예외로 18 = 9+9 로 16+1+1 보다 더 짧게 나타낼 수 있었다.

접근 방법 2 

18 을 자연수 2개의 합으로 나타낸다고 했을 때, 그 경우의 수를 모두 검사해서 최소가 될 때를 찾았다.

(1, 17)

(2, 16)

(3, 15)

(4, 14)

(5, 13)

(6, 12)

(7, 11)

(8, 10)

(9, 9) 

그러나 시간 초과가 떴다. 다시 생각해보니 이 중에 최소가 될 수 있는 후보는 제곱수가 포함된 경우였다.

그래서 1,4,9,16이 포함된 경우만 다시 검사해서 최소일 때를 찾아주었다.

즉,

dp[18-1] + dp[1]  => (16+1)+1

dp[18-4] + dp[4] =>  (9+4+1)+4

dp[18-9] + dp[9]  => 9 + 9

dp[18-16] + dp[16] => (1+1)+16

#include <iostream>
#include <algorithm>

using namespace std;

int dp[100489] = {0};

int main(){
     for(int i = 1; i<=100000; i++){
         dp[i] = 10000;
     }
    
    int N;
    cin >> N;

    dp[0] = 0; dp[2] = 2; dp[3] = 3;
    for(int i = 1; i*i<=100000; i++){
        dp[i*i] = 1;
    }
    
    for(int i = 1; i<=316; i++){
        for(int j = i*i+1; j<=(i+1)*(i+1)-1; j++){
            for(int k = 1; k<=i; k++){
                dp[j] = min(dp[j], dp[j-k*k] + dp[k*k]);
            }
        }
    }

        cout << dp[N];

    
    
    return 0;
}

문제 링크 : www.acmicpc.net/problem/15990

문제

정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 3가지가 있다. 합을 나타낼 때는 수를 1개 이상 사용해야 한다. 단, 같은 수를 두 번 이상 연속해서 사용하면 안 된다.

• 1+2+1
• 1+3
• 3+1

정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 정수 n이 주어진다. n은 양수이며 100,000보다 작거나 같다.

출력

각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 1,000,000,009로 나눈 나머지를 출력한다.

접근 방법

문제의 조건에서 유의해야 할 점이 있다.

1) 1+3과 3+1 이 다름.

2) 같은 수를 두 번 이상 연속해서 사용할 수 없음.

일단 규칙을 찾기 위해 쭉 써보았다.

dp[1] = 1 (1)  (단일 숫자)

dp[2] = 1 (2) (단일 숫자)

dp[3] = dp[2]에 1을 더하는 경우 (2+1 -> 1가지)

          + dp[1]에 2를 더하는 경우 (1+2 -> 1가지)

          + dp[0]에 3을 더하는 경우 (0+3 -> 1가지)

          = 1 + 1 + 1 =3 

dp[4] = dp[3]에 1을 더하는 경우 (1+2+1 , 0+3+1 -> 연속 제외하고 2가지)

          + dp[2]에 2를 더하는 경우 (연속 제외하고 0가지)

          + dp[1]에 3을 더하는 경우 (1+3 -> 1가지)

          = 2 + 0 + 1 = 3

dp[5] = dp[4]에 1을 더하는 경우 (1+3+1 -> 연속 제외하고 1가지)

          + dp[3]에 2를 더하는 경우 (2+1+2, 0+3+2 -> 연속 제외하고 2가지)

          + dp[2]에 3을 더하는 경우 (2+3 -> 1가지)

          = 1 + 2 + 1 = 4

dp[6] = dp[5]에 1을 더하는 경우 (2+1+2+1, 0+3+2+1, 2+3+1 -> 연속 제외하고 3가지)

          + dp[4]에 2를 더하는 경우 (1+2+1+2, 0+3+1+2, 1+3+2 -> 3가지)

          + dp[3]에 3을 더하는 경우 (2+1+3, 1+2+3 -> 연속 제외하고 2가지)

          = 3 + 3 + 2 = 8

dp[7] = dp[6]에 1을 더하는 경우 (1+2+1+2+1, 0+3+1+2+1, 1+3+2+1  / 2+1+3+1, 1+2+3+1 -> 연속 제외하고 5가지)

          + dp[5]에 2를 더하는 경우 (1+3+1+2, 2+3+2 -> 연속 제외하고 2가지)

          + dp[4]에 3을 더하는 경우 (1+2+1+3, 0+3+1+3 -> 연속 제외하고 2가지)

          = 5 + 2 + 2 = 9

dp[n] = arr1[n] + arr2[n] + arr3[n] 으로 분할해서 더한다고 하자. (RHS의 각 배열은 +1, +2, +3 하는 경우이다.)

그러면

arr1[n] = arr2[n-1] + arr3[n-1]

arr2[n] = arr1[n-2] + arr3[n-2]

arr3[n] = arr1[n-3] + arr2[n-3] 

인 규칙을 찾을 수 있다. (위에 색칠해놓은 글씨를 보면 이해하기 쉽다.)

#include <iostream>

using namespace std;

long long dp[100001] = {0};
long long arr1[100001] = {0};
long long arr2[100001] = {0};
long long arr3[100001] = {0};


int main(){
    
        
    int TC; cin >> TC;

    arr1[3] = 1;    arr1[4] = 2;    arr1[5] = 1;
    arr2[3] = 1;    arr2[4] = 0;    arr2[5] = 2;
    arr3[3] = 1;    arr3[4] = 1;    arr3[5] = 1;
    
    dp[0] = 1; dp[1] = 1; dp[2] = 1;
    for(int i = 3; i<=5; i++) {dp[i] = (arr1[i] + arr2[i] + arr3[i]) % 1000000009;}
    
    for(int i = 6; i<=100000; i++){
        arr1[i] = (arr2[i-1] + arr3[i-1]) % 1000000009;
        arr2[i] = (arr1[i-2] + arr3[i-2]) % 1000000009;
        arr3[i] = (arr1[i-3] + arr2[i-3]) % 1000000009;
        dp[i] = (arr1[i] + arr2[i] + arr3[i]) % 1000000009;
    }
    
    
    for(int t = 0; t<TC; t++){
        
        int n;
        cin>>n;
        
        cout << dp[n] << "\n";
        
        
    }
    
    
    return 0;
}

주의할 점

int 형은 더할 때 범위가 넘어가므로 long long 자료형을 사용해야 한다.

그리고 for 문 안에서 arr1[], arr2[], arr3[] 을 구할 때도 Mod 연산을 적용해서 저장해야 한다. 

문제 링크 : www.acmicpc.net/problem/11052

문제

요즘 민규네 동네에서는 스타트링크에서 만든 PS카드를 모으는 것이 유행이다.

PS카드는 PS(Problem Solving)분야에서 유명한 사람들의 아이디와 얼굴이 적혀있는 카드이다. 각각의 카드에는 등급을 나타내는 색이 칠해져 있고, 다음과 같이 8가지가 있다.

• 전설카드
• 레드카드
• 오렌지카드
• 퍼플카드
• 블루카드
• 청록카드
• 그린카드
• 그레이카드

카드는 카드팩의 형태로만 구매할 수 있고, 카드팩의 종류는 카드 1개가 포함된 카드팩, 카드 2개가 포함된 카드팩, ... 카드 N개가 포함된 카드팩과 같이 총 N가지가 존재한다.

민규는 카드의 개수가 적은 팩이더라도 가격이 비싸면 높은 등급의 카드가 많이 들어있을 것이라는 미신을 믿고 있다. 따라서, 민규는 돈을 최대한 많이 지불해서 카드 N개 구매하려고 한다. 카드가 i개 포함된 카드팩의 가격은 Pi원이다.

예를 들어, 카드팩이 총 4가지 종류가 있고, P1 = 1, P2 = 5, P3 = 6, P4 = 7인 경우에 민규가 카드 4개를 갖기 위해 지불해야 하는 금액의 최댓값은 10원이다. 2개 들어있는 카드팩을 2번 사면 된다.

P1 = 5, P2 = 2, P3 = 8, P4 = 10인 경우에는 카드가 1개 들어있는 카드팩을 4번 사면 20원이고, 이 경우가 민규가 지불해야 하는 금액의 최댓값이다.

마지막으로, P1 = 3, P2 = 5, P3 = 15, P4 = 16인 경우에는 3개 들어있는 카드팩과 1개 들어있는 카드팩을 구매해 18원을 지불하는 것이 최댓값이다.

카드 팩의 가격이 주어졌을 때, N개의 카드를 구매하기 위해 민규가 지불해야 하는 금액의 최댓값을 구하는 프로그램을 작성하시오. N개보다 많은 개수의 카드를 산 다음, 나머지 카드를 버려서 N개를 만드는 것은 불가능하다. 즉, 구매한 카드팩에 포함되어 있는 카드 개수의 합은 N과 같아야 한다.

입력

첫째 줄에 민규가 구매하려고 하는 카드의 개수 N이 주어진다. (1 ≤ N ≤ 1,000)

둘째 줄에는 Pi가 P1부터 PN까지 순서대로 주어진다. (1 ≤ Pi ≤ 10,000)

출력

첫째 줄에 민규가 카드 N개를 갖기 위해 지불해야 하는 금액의 최댓값을 출력한다.

접근 방법 1) 

dfs로 풀었는데 역시 시간초과가 떴다 .

#include <iostream>
#include <vector>

using namespace std;

int N;
int P[1001] = {0};
vector<int> vec;
int maxSum = 0;

void dfs(int sum, int idx){
    
    if(sum>N) return;
    
    if(sum==N){
        int ans=0;
        for(int i=0; i<vec.size(); i++){
            ans += vec[i];
        }
        if(maxSum<ans){maxSum = ans;}
        
        
        return;
    }
    for(int i = 1; i<=N; i++){
        
        if(idx<=i){
            sum+=i;
            vec.push_back(P[i]);
            dfs(sum, i);
            sum-=i;
            vec.pop_back();
        }
    }
}

int main(){
    
    
   
    cin >> N;
    for(int i = 1; i<=N; i++){
        cin >> P[i];
    }
    dfs(0,0);
    cout << maxSum;
    
    
    
    return 0;
}

접근 방법 2)

 dp로 풀어야 시간 안에 문제를 풀 수 있을 것이다.

먼저 N = 3일 때, 어떤 카드팩 조합이 최대 금액이 될 것인가?

dp[n] 을 n개의 카드를 구매하는데에 필요한 최대 금액이라고 하자.

그러면 dp[3] 은 

dp[3-1] + P[1]

dp[3-2] + P[2] 

dp[3-3] + P[3]  (카드 팩 1개 통째로 사는 경우)

중 가장 큰 값이 될 것이다. 이는 아래와 같이 나타낼 수 있다. 

for(int j = 1; j<=i; j++){

      dp[i] = max(dp[i], dp[i-j] + P[j]);

}

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int N;
int P[1001] = {0};
int dp[1001] = {0};
vector<int> vec;
int maxSum = 0;



int main(){
    
    cin >> N;
    for(int i = 1; i<=N; i++){
        cin >> P[i];
    }

    dp[0] = 0;
    dp[1] = P[1];
    
    for(int i = 2; i<=N; i++){
        for(int j = 1; j<=i; j++){
            dp[i] = max(dp[i], dp[i-j] + P[j]);
        }
    }
    
    cout<<dp[N];
    
    return 0;
}

문제 링크 : www.acmicpc.net/submit/11727/26381160

문제

2×n 직사각형을 1×2, 2×1과 2×2 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오.

아래 그림은 2×17 직사각형을 채운 한가지 예이다.

입력

첫째 줄에 n이 주어진다. (1 ≤ n ≤ 1,000)

출력

첫째 줄에 2×n 크기의 직사각형을 채우는 방법의 수를 10,007로 나눈 나머지를 출력한다.

접근 방법

가로의 길이가 1부터 n이 될 때까지 타일을 붙여나가며, 이때 두가지 케이스로 나눠서 경우의 수를 카운트했다.

붙여야하는 타일의 가로 길이가 1인 것과 2인 것을 나눴다.

Case 1) 가로 길이가 1인 타일을 붙여야 하는 경우

이 경우는 타일의 길이가 n-1가 되도록 붙이는 경우의 수와 같다. 길이가 n인 타일을 만드려면 n-1 타일에 2x1 타일을 추가하기만 하면 되기 때문이다.

Case 2) 가로 길이가 2인 타일을 붙여야 하는 경우

이 경우엔 두가지 경우로 또 나눠서 생각해야한다. 

2-1) 1x2 타일을 붙이는 경우(세로로 두개)

이 경우는 타일의 길이가 n-2가 되도록 붙이는 경우의 수와 같다. 길이가 n인 타일을 만드려면 n-2 타일에 1x2 타일 두개를 세로로 추가하기만 하면 되기 때문이다.

2-2) 2x2 타일을 붙이는 경우 

이 경우도 2-1과 같다. 2x2 타일을 추가만 하면 된다.

Case 1, 2를 조합해서 생각하면, 길이 n인 타일을 붙이는 경우의 수는,

길이 n-1인 타일을 붙이는 경우의 수 + 2*(길이 n-2인 타일을 붙이는 경우의 수) 로 나타낼 수 있다.

즉, dp[n] = dp[n-1] + 2*dp[n-2]인 것이다.

#include <iostream>
#include <vector>

using namespace std;

int dp[1001] = {0};

int main(){
    
    int n;
    cin >> n;
    
    dp[0] = 0;
    dp[1] = 1;
    dp[2] = 3;
    
    for(int i = 3; i<=n; i++){
        dp[i] = (2*dp[i-2] + dp[i-1]) % 10007;
    }
    cout << dp[n];
    
    return 0;
}

이때 주의할 점은 for문 안에서 dp[n] = dp[n-1] + 2*dp[n-2] 로 계산을 쭉 하고

마지막에 출력할 때 dp[n]%10007 을 하면 안된다는 것이다. 위의 코드와 같이 for문 안에서 나머지 계산을 해줘야한다.

문제 요구조건 자체가 mod 연산을 한 결과를 출력하라고 했으니, 처음에 dp[]에 값을 저장할 때 mod연산의 결과를 저장해야한다.

문제 링크 : www.acmicpc.net/problem/10972

문제

1부터 N까지의 수로 이루어진 순열이 있다. 이때, 사전순으로 다음에 오는 순열을 구하는 프로그램을 작성하시오.

사전 순으로 가장 앞서는 순열은 오름차순으로 이루어진 순열이고, 가장 마지막에 오는 순열은 내림차순으로 이루어진 순열이다.

N = 3인 경우에 사전순으로 순열을 나열하면 다음과 같다.

• 1, 2, 3
• 1, 3, 2
• 2, 1, 3
• 2, 3, 1
• 3, 1, 2
• 3, 2, 1

입력

첫째 줄에 N(1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄에 순열이 주어진다.

출력

첫째 줄에 입력으로 주어진 순열의 다음에 오는 순열을 출력한다. 만약, 사전순으로 마지막에 오는 순열인 경우에는 -1을 출력한다.

접근 방법 1)

1~N 의 숫자로 이루어진 순열을 dfs로 구하는데, 차근차근 구해나가면서 입력한 순열과 일치할 때를 찾는다. 

찾으면 flag = true 로 바꾼 뒤, 다음 턴에서 다음 차례의 순열을 출력하고 stop = true로 바꿔서 탐색을 멈춘다.

그러나 이 방법으로는 시간 초과가 떴다. STL을 이용해보자.

#include <iostream>
#include <vector>

using namespace std;

int N;
vector<int> vec;
vector<int> ans;
vector<int> greaterVec;
int visited[10000] = {0};

bool flag = false;
bool stop = false;

bool lastChk(){
    
    int n = N;
    bool ret = false;
    for(int i = 0; i<N; i++){
        if(vec[i] == n) {
            ret = true;
            n--;
        }
        else {
            ret = false;
            break;
        }
    }
    return ret;
    
    
}



void search(int toPick){
    
   

    if(toPick==0){
        
        if(flag){
            for(int i = 0; i<ans.size(); i++){
                cout << ans[i] << " ";
            }
            cout << "\n";
            stop = true;
            return;
        }
        int cnt=0;
        for(int i = 0; i<ans.size(); i++){
            if(ans[i]==vec[i]) cnt++;
            else break;
        }
        
        if(cnt==N) {
            flag = true;
           // return;
        }
    }
    
    
    for(int i = 0; i<greaterVec.size(); i++){
        
        if(visited[i] == 0){
            visited[i] = 1;
            ans.push_back(greaterVec[i]);
            search(toPick-1);
            ans.pop_back();
            visited[i] = 0;
            if(stop) {return;}
        }
    }
    
}

int main(){
    
    cin >> N;
    
    int num;
    for(int i = 0; i<N; i++){
        cin >> num;
        vec.push_back(num);
        greaterVec.push_back(i+1);
    }
    
    
    
    if(lastChk()) {
        cout << -1;
    }
    else{
        search(N);
    }
    
    return 0;
}

접근 방법 2)

next_permutation 함수를 이용했다. 이 함수는 vec의 원소 순서 자체를 바꿔버리며 마지막 순열 다음에는 false를 리턴한다. 이 경우는 문제의 요구 조건에 맞게 -1을 출력해주면 된다. 위의 방법보다 매우 간단하게 해결할 수 있는 방법이다. 

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int N;
vector<int> vec;

int main(){


    cin >> N;
    int num;
    for(int i = 0; i<N; i++){
        cin >> num;
        vec.push_back(num);
    }


    if(next_permutation(vec.begin(), vec.end())){
        
        for(int i = 0; i<N; i++){
            cout << vec[i] << " ";
        }
    }
    else{
        cout << -1;
    }
        
        

   

    return 0;
}

문제 링크 : www.acmicpc.net/problem/11723

문제

비어있는 공집합 S가 주어졌을 때, 아래 연산을 수행하는 프로그램을 작성하시오.

• add x: S에 x를 추가한다. (1 ≤ x ≤ 20) S에 x가 이미 있는 경우에는 연산을 무시한다.
• remove x: S에서 x를 제거한다. (1 ≤ x ≤ 20) S에 x가 없는 경우에는 연산을 무시한다.
• check x: S에 x가 있으면 1을, 없으면 0을 출력한다. (1 ≤ x ≤ 20)
• toggle x: S에 x가 있으면 x를 제거하고, 없으면 x를 추가한다. (1 ≤ x ≤ 20)
• all: S를 {1, 2, ..., 20} 으로 바꾼다.
• empty: S를 공집합으로 바꾼다. 

입력

첫째 줄에 수행해야 하는 연산의 수 M (1 ≤ M ≤ 3,000,000)이 주어진다.

둘째 줄부터 M개의 줄에 수행해야 하는 연산이 한 줄에 하나씩 주어진다.

출력

check 연산이 주어질때마다, 결과를 출력한다.

접근 방법 1)

x의 범위가 1부터 20까지이니 크기가 21인 배열을 만들어서, S에 x 가 있으면 arr[x] = 1로 없으면 arr[x] = 0으로 표시했다.

cin이 M만큼 반복되므로 처음에는 시간 초과가 났으나 

ios_base::sync_with_stdio(0);

cin.tie(0);

을 추가해주니 시간초과가 해결 되었다.

#include <iostream>
#include <cstring>

using namespace std;


int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    
    string str = "";
    int M, x;
    int arr[21] = {0};
    
    
    cin >> M;
    for(int i = 0; i<M; i++){
        cin >> str;
        
        if(str=="add"){
            cin >> x;
            if(arr[x]==0){   //없으면
                arr[x] = 1;
            }
        }
        
        else if(str=="remove"){
            cin >> x;
            if(arr[x] == 1){  //있으면
                arr[x] = 0;
            }
            
        }
        else if(str=="check"){
            cin >> x;
            if(arr[x] == 0){   //없으면
                cout << "0\n";
            } else{
                cout << "1\n";
            }
        }
        else if(str=="toggle"){
           cin >> x;
            if(arr[x] == 1){  //있으면
                arr[x] = 0;
            } else{
                arr[x] = 1;
            }
        }
        else if(str=="all"){
            
            for(int k = 1; k<=20; k++){ arr[k] = 1;}
            
        }
        else if(str=="empty"){
            memset(arr, 0, sizeof(arr));
        }
    }
    
    return 0;
}

접근 방법 2)

해당 문제는 백준의 브루트포스 - 비트마스크 문제이다. 비트 마스크로도 문제를 풀어 보았다.

[비트마스크 정리]

s 에 숫자가 있으면 그 숫자 인덱스가 가리키는 비트를 1로 표시하는 방식으로 문제를 해결했다.

첫번째 그림의 1 : 1 << 1   (0000 0010)

두번째 그림의 2 : 1 << 2  (0000 0100)

두번째 그림의 3 : 1 << 3  (0000 1000)

위 그림에서는 나타낼 수 있는 숫자가 0~7 뿐이지만, s를 int형(4byte=32bit) 으로 잡았기 때문에 0~32 숫자가 s에 포함되는지 안 되는지 판단할 수 있고, 문제에서 x는 1~20이기 때문에 충분하다.

추가 : 입력한 숫자와 S를 or 연산 시킨다. 

삭제 : 입력한 숫자를 not 시키고 그 수를 S와 and 연산한다.

체크 : S에 입력한 숫자가 있으면,  둘을 and 연산 한 결과가 1일 것이다. S = {1,2} , check 1이면 

          S = 0000 0110

  (1<<1) = 0000 0010

      and = 0000 0010   

이므로 1번째 자리가 1이어서 if 조건절 안이 true 가 된다.

#include <iostream>
#include <cstring>

using namespace std;


//비트마스크로 풀기

int main(){
    
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    
    string str = "";
    int M, x;
    
    int S = 0;
   
    cin >> M;
    for(int i = 0; i<M; i++){
        cin >> str;
        
        if(str=="add"){
            cin >> x;
            S |= (1<<x);
        }
        
        else if(str=="remove"){
            cin >> x;
            S &= ~(1<<x);
        }
        else if(str=="check"){
            cin >> x;
            if(S & (1<<x)){   //있으면
                cout << "1\n";
            } else{
                cout << "0\n";
            }
        }
        else if(str=="toggle"){
           cin >> x;
            if(S & (1<<x)){  //있으면
                S &= ~(1<<x); //없애고
            } else{             //없으면
                S |= (1<<x);     //추가
            }
        }
        else if(str=="all"){
            S = (1<<21) - 1;
        }
        else if(str=="empty"){
            S = 0;
        }
        
    
    }
    
    return 0;
}

큰 차이는 나지 않는다.