[백준/BOJ] 15649번, 15651번: N과 M (백트래킹 기법) - C++ 문제 풀이

문제 설명

 

문제 링크: https://www.acmicpc.net/problem/15649

 

풀이

이 문제는 1부터 N까지의 수를 가지고 M 길이의 수열을 만들어 출력하는 문제입니다.

그런데, 같은 수를 사용해서 수열을 만들 수 없습니다.

 

15651번 문제는 위 문제와 같은 데, 차이점은 같은 수를 사용해서 수열을 만들 수 있다는 점이 다를 뿐입니다.

우선 이 문제를 푼 후, 이를 확장해서 15651번 문제를 해결하겠습니다.

 

이 문제는 커다란 자루에 N개의 공을 넣고, 한 개씩 뽑아 나열하는 것과 같습니다.

그럼 어떻게 뽑아야 모든 경우의 수열을 만들 수 있을까요?

 

예를 들어, N = 8, M = 2라고 해보죠.

 

1. 첫 번째 공을 뽑습니다.

   공에 있는 숫자를 기록하고, 자루에서 뺍니다.

 

2. 두 번째 공을 뽑습니다. 

    이제 길이가 2가 되었으니, 전에 뽑은 숫자와 함께 수열을 기록합니다.

    자루에서 두 번째 공을 뺍니다.

 

3. 첫 번째 공을 뽑은 때로 돌아가,  다시 두 번째 공을 뽑습니다.

    이 과정을 자루에 있는 공이 모두 떨어질 때까지 반복합니다.

    그리고, 이 과정이 끝나면 첫 번째 공의 숫자로 시작하는 수열을 모두 만들 수 있습니다.

 

     이렇듯 이전 상태로 되돌아가 문제를 해결하는 방식을 백트래킹(Back tracking)이라고 합니다.  

     백트래킹 기법으로 유명한 문제로 N-Queen 문제가 있습니다.

     자세한 내용은 여기서 찾아보실 수 있습니다.

[백준/BOJ] 9663번: N-Queen (백트래킹 기법) - C++ 문제 풀이

 

 

4. 빼낸 공을 모두 자루에 되돌린 후, 다른 숫자의 공을 첫 번째 공으로 하여

    1번 과정부터 다시 반복.

 

이제, 위 과정을 코드로 바꾸는 것만 남았네요.

그런데, 자루에서 공을 빼는 것을 어떻게 바꾸면 좋을까요?

벡터나 리스트 등을 써서 말 그대로 원소를 뺐다가 다시 되돌리는 방법도 있지만, 단지 수열을 구하기 위해선 너무 무겁습니다.

그래서, 플래그를 써서 표시를 했습니다. 플래그가 1이면 아직 자루 안에 남아 있고, 0이면 자루에서 뺀 것으로 약속하고 코드를 바꾸면 다음과 같습니다.

N = 8;
M = 2;

// 처음에는 모든 공이 자루에 들어있음
for(int i = 0; i < N; i++){
    flags[i] = 1;
}

void M_sequence(int len, const string& str){

    if (len == M){
        cout << str << "\n";	// 만들어진 수열을 출력
        return;
    }    

    for( int i = 0; i < N; i++){

        if ( flags[i]){
        
            flags[i]--;	// 자루에서 공을 뺀다

            string strN = str + to_string(i+1) + " ";	// 공의 숫자를 기록
            
            M_sequence(len+1, strN);  // 다음 공을 고르기  

            flags[i]++;	// 공을 자루에 되돌린다.
        }
    }
}

 

이제, 15651번 문제를 생각해 보죠.

문제 링크: https://www.acmicpc.net/problem/15651

 

15651번 문제에서, 숫자의 중복을 같은 숫자의 공이 여러 개 들어있는 것으로 생각하면 되겠네요.

위의 코드에서, 한 개의 공에서 N개의 공을 가지고 시작한다는 것으로 바꿔주면 됩니다.

그럼 flags [i] 값이 0이 될 때까지, i+1 숫자가 수열에 계속 나타날 수 있습니다.

// 처음에는 모든 공이 자루에 들어있음
for(int i = 0; i < N; i++){
    flags[i] = N;	// 1 -> N
}

 

 

소스 코드

15649번 소스 코드

#include <iostream>
#include <string>
using namespace std;

#define NUM     8
int flags[NUM];

int N;
int M;

void M_sequence(int len, const string& str){

    if (len == M){
        cout << str << "\n";
        return;
    }    

    for( int i = 0; i < N; i++){

        if ( flags[i]){
        
            flags[i]--;

            string strN = str + to_string(i+1) + " ";
            
            M_sequence(len+1, strN);    

            flags[i]++;
        }
    }
}

int main(){

    ios::sync_with_stdio(false);
    cout.tie(NULL);
    
    cin >> N >> M;

    for(int i = 0; i < N; i++){
        flags[i] = 1;	// 1로 초기화 
    }

    string str;

    M_sequence(0, str);

    return 0;
}

 

 

15651번 소스 코드

#include <iostream>
#include <string>
using namespace std;

#define NUM     8
int flags[NUM];

int N;
int M;

void M_sequence(int len, const string& str){

    if (len == M){
        cout << str << "\n";
        return;
    }    

    for( int i = 0; i < N; i++){
        
        if ( flags[i]){
            flags[i]--;

            string strN = str + to_string(i+1) + " ";
            
            M_sequence(len+1, strN);    
            
            flags[i]++;
        }
    }
}

int main(){

    ios::sync_with_stdio(false);
    cout.tie(NULL);
    
    cin >> N >> M;

    for(int i = 0; i < N; i++){
        flags[i] = N;	// N으로 초기화
    }

    string str;

    M_sequence(0, str);

    return 0;
}