[알고리즘 문제] 백준6603 -로또

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

6603번: 로또

 

순열 + 오름차순 문제입니다.  오름차순 문제인 지 몰라서 순열을 개수만큼 출력하는 것 인 줄 알았는데 다시 풀었습니다.

처음에 구현한 방법은 좀 무식한 방법으로 구했습니다.

 

1. 첫번째 방법 

출력해야할 개수는 k개 중에서 6개를 뽑아야 하기 때문에 kC6입니다. 먼저 이 값을 구하는데 팩토리얼이 필요하기 떄문에 팩토리얼 함수도 따로 만들었습니다. 그리고 재귀를 사용해서 길이가 6인 순열을 만드는데, 만들때마다 오름차순인지 검사합니다. 만약 오름차순이면 출력해 줍니다. 그래도 일단 문제를 풀긴 했습니다.

 

2. 두번째 방법

첫번째 방법은 일단 필요없는 순열까지 구해야하고, 팩토리얼 구하는 함수, 오름차순인지 검사하는 함수... 쓸대 없는 부분이 너무 많습니다. 이 문제를 풀면서 "오름차순"부분을 간단하게 해결할 수 있을 것 같다는 생각을 했습니다. 재귀를 돌때 index값을 하나씩 증가해주면, 다음 함수에서의 index값은 무조건 이전 함수의 index값보다 크다는 아이디어 였습니다. 

 

#include <iostream>

using namespace std;

int arr[14];
int temp[6];
int k;

void recur(int index, int depth)
{

    if (depth == 6)
    {
        for (int k = 0; k < 6; k++)
        {
            cout << temp[k] << " ";
        }
        cout << "\n";
        return;
    }
    for (int i = index; i < k; i++)
    {
        temp[depth] = arr[i];
        recur(i + 1, depth + 1);
    }
}

int main()
{

    while (1)
    {
        cin >> k;
        if (k == 0)
        {
            break;
        }

        for (int i = 0; i < k; i++)
        {
            int n;
            cin >> n;
            arr[i] = n;
        }

        recur(0, 0);

        cout << "\n";
    }

    return 0;
}