[Algorithm] Baekjoon 15666번 : N과M (12)

https://www.acmicpc.net/problem/15666

15666번: N과 M (12)

int maxCount = 0;
int maxNum = 0;
 
bool visited[9];
int arr[9];
vector<int> v;
 
void recur(int start, int count) 
{
    if (count == maxCount)
    {
        for (int i = 0; i < count; i++)
        {
            printf("%d ", arr[i]);
        }
        printf("\n");
        return;
    }
 
    int prevNum = 123;
    for (int i = start; i < maxNum; i++) 
    {
        if (prevNum != v[i])
        {
            prevNum = v[i];
            arr[count] = v[i];
            recur(i, count + 1); // 자기자신 또 뽑으면 안될때 i+1, 또뽑아야하면 걍 i
        }
    }
}
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
 
    int n = 0;
    int m = 0;
    int input = 0;
 
    cin >> n >> m;
 
    for (int i = 0; i < n; i++)
    {
        cin >> input;
        v.push_back(input);
    }
 
    sort(v.begin(), v.end());
 
    maxNum = n;
    maxCount = m;
 
    recur(0, 0);
}

 

solved.ac의 class4문제를 풀기 시작했는데, N과M 시리즈가 있어서 먼저 전부 풀었다.

기본적으로 DFS로 푸는 문제인데, 맨 처음문제인 N과M(2)에서 헤매다가 다른 사람 풀이보고 좀 감을 잡았다.

이후 N과M 4,5,8,9,12 를 연달아 풀었는데, 뭔가 기본기를 탄탄히하는 문제들 같았다.

기본적으로 같은 N과M문제들이다 보니 코드를 조금씩만 수정해도 그다음껏들이 풀리는 경우가 많은데,

결국 문제를 잘 알아야 조금만 수정해서 풀든가 말든가 하는것이라서...

 

특정번호 이후에는 1부터 N까지가 아니라, 들어오는 값이 따로있기 때문에 인덱스로 바꿔서 문제를 풀어야 한다.

인풋으로 오는값들은 중복되는 숫자가 있을 수 있다.

그러나, 출력엔 반드시 중복되는 값이 있어서는 안된다.

일단 기본적으로 N과M는 값을 오름차순으로 출력해야하니 인풋값들을 sort한번 해주고 문제를 풀면 된다.

 

이 문제에선 자기자신을 또 뽑아도 된다.

그렇기 때문에 방문체크를 해줄필요는 없다. 자기자신을 또 뽑아야하기 때문에 다음 재귀에도 인덱스를 그대로 넘겨준다.

prevNum 체크가 있는 이유는, 인풋값이 중복되서 들어왔을 때 필요하기 때문이다.

1 7 9 9 가 들어오고 n과 m이 4,2 라면, 1,7 이후에 1,9가 두번 나온다. 끝 두자리가 9 9이기 때문에 그런건데,

이런 예외처리를 위해서 prevNum 체크를 해주는 것이다.

 

사실, 같은값에 대한 체크를 나도 처음엔 해쉬기록하는 형태로 짜는게 먼저 생각나긴 했다.

N과M문제는 경우의수가 그래도 좀 제한되어 있는편이라 괜찮을 수도 있지만, 어마무시하게 많은 경우의수라면 문제가 생길 것 같아서 아예 배제했다.