[BOJ/백준] 6603 로또

● [문제번호 6603] 로또

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

6603번: 로또

 

 

● 알아야 할 것

: DFS

: 재귀

 

 

● 풀이 과정

: [520 - 브루트 포스 - 순열] 문제집에 있는 문제

 

: 기본적인 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;
}

 

 

● [백준] - [알고리즘 중급 1/3] - [531 - 브루트 포스 - 재귀 (연습)] 문제집

번호	문제 번호	문제 이름	풀이 링크
1	6603	로또	https://pirateturtle.tistory.com/301
2	1182	부분수열의 합	https://pirateturtle.tistory.com/302
3	14225	부분수열의 합	https://pirateturtle.tistory.com/303
4	14888	연산자 끼워넣기	https://pirateturtle.tistory.com/304
5	15658	연산자 끼워넣기 (2)	https://pirateturtle.tistory.com/305
6	14500	테트로미노	https://pirateturtle.tistory.com/306
7	16197	두 동전	https://pirateturtle.tistory.com/307
8	16198	에너지 모으기	https://pirateturtle.tistory.com/308
9	9663	N-Queen	https://pirateturtle.tistory.com/309
10	2580	스도쿠	https://pirateturtle.tistory.com/310
11	4574	스도미노쿠	https://pirateturtle.tistory.com/311
12	1987	알파벳	https://pirateturtle.tistory.com/312