[C++] 15663 : N과 M(9)

 

15663번: N과 M (9)

 

겨우 이 문제로 한 시간 넘게 해맸다는게 현타,,,제대로 알기 위해 왜 틀렸는지 하나하나 정리해보려고 한다.

---

[ 틀린 제출 1 ] 

#include <iostream>
#include <algorithm>
#define MAX 9
using namespace std;

int n,m;
int arr[MAX] = {0,};
int visited[MAX] = {0,};
int res[MAX] = {0,};

void dfs(int cnt)
{
    if(cnt == m) //cnt == m이면 결과 배열 차례로 출력 
    {
        for(int i = 0; i < m; i++) 
            cout << res[i] << ' ';
        cout << '\n';
        return;
    }
    //결과가 m보다 작다면 재귀 호출 
    for(int i = 0; i < n; i++)
    {
            if(visited[i] == 0 && res[cnt]!=arr[i]){ 
            // 그 전 결과의 마지막 배열값과 현재 재귀 돌고자 하는 값이 동일한지 비교
            // 동일하지 않다면 -> 재귀, 동일하다면 -> 재귀 돌지 않음
                visited[i] = 1;
                res[cnt] = arr[i];
                dfs(cnt+1);
                visited[i] = 0;
            }
    }
}

int main() {
    cin >> n >> m;    
    for(int i=0; i<n; i++){
        cin>>arr[i];
    }
    sort(arr, arr+n);
    dfs(0);
}

 

일단 이 코드대로 예제를 돌리면 모두 올바른 결과가 나온다. 이 코드의 흐름을 나타내면 다음과 같다. 

n = 4, m = 2, arr[4] = {9,7,9,1} , arr는 정렬하면 {1,7,9,9}

1 7 -> 1 9 이후 그 다음 1 9 에서는 res[cnt] 가 아직 9이고, 입력되고자 하는 값 arr[3]도 9이기 때문에 그 다음 재귀를 돌지 못한다. 

예제가 모두 맞아 정답이구나 했는데 1%도 못 가고 죽어버렸다...,,,

 

다양한 예제 값들을 넣어보니 반례가 있었다. n = 3, m = 3, arr[3] = { 9,3,9 } 인 경우를 생각해보자. 

res의 가장 앞이 3이 되고, 399라는 첫번째 res가 생긴다. 그 다음 39에서 res[1]과 9가 동일하기 때문에 res는 여전히 399이다.

res의 가장 앞이 9가 될 때(9와 3은 같지 않아 재귀가 호출된다.) res는 999가 되고, 그 다음 3이 입력되면 res는 939가 된다. 그리고 마지막 9가 입력될 때 res[2]와 값이 동일하기 때문에 재귀가 호출되지 않는다. 문제가 여기서 발생한다. 원래대로라면 399 939 993 세가지의 출력 결과가 나와야 하는데 939가 안 나오는 것이다. 

 

---

[ 틀린 제출 2 ] 

#include <iostream>
#include <algorithm>
#define MAX 9
using namespace std;

int n,m;
int arr[MAX] = {0,};
int visited[MAX] = {0,};
int res[MAX] = {0,};
int tmp = 0;

void dfs(int cnt)
{
    if(cnt == m) //cnt == m이면 결과 배열 차례로 출력 
    {
        for(int i = 0; i < m; i++) 
            cout << res[i] << ' ';
        cout << '\n';
        return;
    }
    //결과가 m보다 작다면 재귀 호출 
    tmp = 0;
    for(int i = 0; i < n; i++)
    {
        if(visited[i] == 0 && tmp!=arr[i]){ 
            visited[i] = 1;
            res[cnt] = arr[i]; 
            tmp = res[cnt]; //res[cnt] 대신 tmp 사용
            dfs(cnt+1);
            visited[i] = 0;
        }
    }
}

int main() {
    cin >> n >> m;    
    for(int i=0; i<n; i++){
        cin>>arr[i];
    }
    sort(arr, arr+n);
    dfs(0);
}

 

그럼 res[cnt] 대신 tmp 값을 따로 사용하면 되겠구나 했는데 이것도 틀렸다... 

전역변수로 tmp를 설정해두었기 때문이었다. 전역변수로 설정해두면 맨 처음에 고르는 수가 전에 골랐던 수의 영향을 받게 된다. 따라서 지역 변수로 설정한 후 계속 초기화해주어야 한다. 

---

[ 결과 ] 

#include <iostream>
#include <algorithm>
#define MAX 9
using namespace std;

int n,m;
int arr[MAX];
int visited[MAX];
int res[MAX];

void dfs(int cnt)
{
    if(cnt == m)
    {  
        for(int i = 0; i < m; i++){
            cout << res[i] << ' ';
        }
        cout << '\n';
        return;
    }
    int tmp = 0;
    for(int i = 0; i < n; i++)
    {
        if(visited[i] == 0 && tmp!=arr[i]){
            res[cnt] = arr[i];
            tmp = res[cnt];
            visited[i] = 1;
            dfs(cnt+1);
            visited[i] = 0;   
        }
    }
}

int main() {
    cin >> n >> m;    
    for(int i=0; i<n; i++){
        cin>>arr[i];
    }
    sort(arr, arr+n);
    dfs(0);
}