[Algorithm] 백준 - 감소하는 수 (1038번)

문제

[백준] 감소하는 수

1038번: 감소하는 수

 

사용 알고리즘

- 백트래킹 (Backtracking)

해결방법

• 감소하는 수는 중복된 숫자를 허용하지 않는다. 이 의미는 nums = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9} 이렇게 10개의 숫자 수열이 있을 때, 해당 수열의 부분수열 찾아, 내림차순 정렬해주면 그게 감소하는 수가 된다.
  • 예를 들면,
    • 하나의 숫자만 뽑아서 부분수열을 만들면 다음과 같다 (10C1)
      {0}, {1}, {2}, , , {7}, {8}, {9}
    • 두개의 숫자를 뽑아서 부분수열을 만드는 경우 (10C2)
      {0, 1} > 10
      {0, 2} > 20
      . . .
      {9, 7} > 97
      {9, 8} > 98
    • 세 개의 숫자를 뽑아서 부분수열을 만드는 경우 (10C3)
      {0, 1, 2} > 210
      {0, 1, 3} > 310
      . . .
      {9, 8, 6} > 986
      {9, 8, 7} > 987
• 이런식으로 부분수열을 찾으면 되는데, 이는 백트래킹으로 구현한다.
  • 재귀 호출에서는 현재 원소를 선택하지 않는 경우와 선택하는 경우 두 가지로 나뉜다. 현재 원소를 선택하지 않고 다음 원소로 이동한 경우와 현재 원소를 선택하고 다음 원소로 이동한 경우를 고려하면서 모든 조합을 생성.
  • 백트래킹을 위해 선택한 원소를 제거하여 이전 상태로 돌아간다.
• 집합 변수를 선언해 백트래킹을 돌면서 만들어진 감소하는 수를 저장하고, N번째 위치의 감소하는 수를 리턴해준다.
  • set의 경우, 내림차순 정렬이 default 이다.

소스코드

사용언어 : c++

#include <iostream>
#include <vector>
#include <set> 
#include <sstream>
#include <algorithm>

using namespace std;
 
int N;
vector<int> nums = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
set<long long> decrease_nums; // 감소하는 수의 집합

// 백트래킹을 이용하여 감소하는 수 찾기
void generate_combination(vector<int>& current, int index) {
    if (index == nums.size()) {
        vector<int> sorted_nums = current; // 내림차순 정렬
        sort(sorted_nums.begin(), sorted_nums.end(), [](int a, int b) {
            return to_string(a) > to_string(b);
        });

        string num = ""; // 감소하는 수 생성
        for (int c : sorted_nums) {
            num += to_string(c);
        }

        long long input;
        istringstream(num) >> input;
        decrease_nums.insert(input);
        return;
    }
 
    // 현재 원소를 선택하지 않고 다음 원소로 이동
    generate_combination(current, index + 1);
 
    // 현재 원소를 선택하고 다음 원소로 이동
    current.push_back(nums[index]);
    generate_combination(current, index + 1);
 
    // 백트래킹을 위해 선택한 원소 제거
    current.pop_back();
}
 
int main() {
    vector<int> current;
    long long result = -1;

    cin >> N;
 
    generate_combination(current, 0);

    if (N < decrease_nums.size()) {
        auto it = decrease_nums.begin();
        advance(it, N);

        result = *it;
    }
    
    cout << result << endl;
 
    return 0;
}

lambda 함수

[캡쳐] (매개변수) -> 반환타입 { 함수 본문 }

* [캡처] : 람다 함수가 외부 변수를 사용할 때, 해당 변수를 캡처할 목록을 지정합니다. 캡처하지 않을 경우 비워둡니다.
* (매개변수) : 함수에 전달될 매개변수 목록을 정의합니다. 매개변수가 없는 경우 비워둡니다.
* -> 반환타입 : 함수의 반환 타입을 지정합니다. 반환 타입이 없는 경우 비워둡니다.
* {} : 람다 함수의 본문을 중괄호로 감싸고 그 안에 코드를 작성합니다.

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

int main() {
    // 간단한 덧셈 람다 함수
    auto add = [](int a, int b) { return a + b; };
    int result = add(3, 5);
    
    // 람다 함수를 사용하여 벡터의 요소 합 구하기
    vector<int> numbers = {1, 2, 3, 4, 5};
    int sum = 0;
    for_each(numbers.begin(), numbers.end(), [&sum](int num) {
        sum += num;
    });

    return 0;
}

 

 

 

isstringstream

* 표준 라이브러리에서 제공하는 클래스로, 문자열을 입력 스트림으로 다루는 데 사용

* 문자열을 공백 문자(스페이스, 탭, 개행 등)로 구분하여 토큰으로 나누고, 각 토큰을 원하는 데이터 타입으로 파싱할 수 있게 해준다.

#include <iostream>
#include <sstream>

using namespace std;

int main() {
    string inputString = "42 3.14 Hello";

    // istringstream 객체 생성 및 문자열 입력
    istringstream iss(inputString);

    int intValue;
    double doubleValue;
    string stringValue;

    // iss로부터 데이터 추출
    iss >> intValue >> doubleValue >> stringValue;

    cout << "정수: " << intValue << endl;
    cout << "실수: " << doubleValue << endl;
    cout << "문자열: " << stringValue << endl;

    return 0;
}

정수: 42
실수: 3.14
문자열: Hello

 

한줄평

처음엔, 감소하는수가 최대로 만들어질 수 있는게 9876543210 이므로, 1부터 while(1)을 돌면서 N번째 감소하는 수를 찾았는데 이렇게 하니까 시간초과가 나왔다(당연한 결과)

{0, 1, 2, 3, 4, 5, 6, 7, 8, 9} 수열에서 숫자를 뽑아 조합으로 풀어야 하는게 이 문제의 킥이다. (킥!)