[BOJ/백준] 6603 로또

● [문제번호 6603] 로또

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

6603번: 로또

 

● 알아야 할 것

: DFS

: 재귀

 

● 풀이 과정

: 기본적인 DFS문제에서 조합을 위한 중복 방지 조건을 추가 한 듯하다.

 

● 주의 할 것

: 순열이 아닌 조합이므로

중복 순열은 제거해야한다.

여기 문제에서는 중복 순열을 제거하기 위해

오름차순이라는 조건을 걸어서 해결하였다.

 

● 참고 할 것

: NULL

 

● 풀이 코드

#include <bits/stdc++.h>

using namespace std;

// S : 각 테스트 케이스의 입력 배열
// num : 각 테스트 케이스의 출력 배열
// visited : 각 테스트 케이스의 방문 여부 확인 배열
int S[13] = {0, };
int num[13] = {0, };
bool visited[13] = {false, };
int K;

// 각 테스트의 조합을 출력
void combination(int cnt)
{
    // num 배열에 숫자가 6개 인 경우
    if(cnt == 6)
    {
        for(int i = 1; i <= 6; i++)
            cout << num[i] << " ";
        cout << "\n";
        
        return ;
    }
    
    // S 배열의 원소 하나씩 순서대로 탐색
    for(int i = 1; i <= K; i++)
    {
        // 방문한 적 없고 오름차순(중복 방지)
        if(!visited[i] && num[cnt] < S[i])
        {
            // 1. 방문 체크인
            // 2. num 배열에 숫자 저장
            // 3. 재귀
            // 4. 방문 체크아웃
            visited[i] = true;
            num[cnt + 1] = S[i];
            combination(cnt + 1);
            visited[i] = false;
        }
    }
}


int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    while(1)
    {
        cin >> K;
        
        if(K == 0)
            break;
        
        // 각 테스트 케이스 입력 배열
        for(int k = 1; k <= K; k++)
            cin >> S[k];
        
        // 조합 출력
        combination(0);
        
        cout << "\n";
    }
    
    return 0;
}

 

 

● [백준] - [알고리즘 기초 2/2] - [520 - 브루트 포스 - 순열] 문제집

번호	문제 번호	문제 이름	풀이 링크
1	10972	다음 순열	https://pirateturtle.tistory.com/237
2	10973	이전 순열	https://pirateturtle.tistory.com/238
3	10974	모든 순열	https://pirateturtle.tistory.com/239
4	10819	차이를 최대로	https://pirateturtle.tistory.com/240
5	10971	외판원 순회 2	https://pirateturtle.tistory.com/241
6	6603	로또	https://pirateturtle.tistory.com/242