[BOJ]6603번: 로또(java, c++)

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

6603번: 로또

 

c++ 코드

방법 1: 순열 응용 - 라이브러리 사용

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main()
{
	while (true)
	{
		// 입력
		int k;
		cin >> k;
		if (k == 0)
		{
			break;
		}
		vector<int> num(k);
		for (int i = 0; i < k; ++i)
		{
			cin >> num[i];
		}
		
		// 위치 정렬을 위해 k길이의 bool 벡터 생성. 6자리만의 값을 true로 가진다. 
		vector<bool> pos(k);
		for (int i = 0; i < 6; ++i)
		{
			pos[i] = true;
		}

		// 역사전순 위치 순서대로, 자릿값이 true인 num[i]를 출력
		do
		{
			for (int i = 0; i < k; ++i)
			{
				if (pos[i])
				{
					cout << num[i] << ' ';
				}
			}
			cout << '\n';

		} while (prev_permutation(pos.begin(), pos.end()));

		cout << '\n';
	}
	
	return 0;
}

 

방법 2: dfs 백트랙킹

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

const int MAX = 6;

void dfs(vector<int> &num, vector<int> &lotto, int index, int depth)
{
	// 6자리가 완성되면 출력
	if (depth == MAX)
	{
		for (int i = 0; i < MAX; ++i)
		{
			cout << lotto[i] << ' ';
		}
		cout << '\n';
		return;
	}
	// 6자리가 완성되기 전에 index가 범위를 넘어버린 경우
	else if (index == num.size())
	{
		return;
	}

	lotto[depth] = num[index];

	// num[index]를 선택하는 경우
	dfs(num, lotto, index + 1, depth + 1);

	// num[index]를 선택하지 않는 경우
	dfs(num, lotto, index + 1, depth);
}

int main()
{
	while (true)
	{
		// 입력
		int k;
		cin >> k;
		if (k == 0)
		{
			break;
		}
		vector<int> num(k);
		for (int i = 0; i < k; ++i)
		{
			cin >> num[i];
		}

		// dfs - 백트랙킹으로 숫자 조합
		vector<int> lotto(MAX);
		dfs(num, lotto, 0, 0);

		cout << '\n';
	}

	return 0;
}

 

java 코드

방법 2: dfs 백트랙킹 

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.List;
 
public class Main {
    
    static List<Integer> listLotto;
    static List<String> listCompleteLotto;
 
    public static void main(String[] args) throws Exception {
 
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
 
        String line = "";
        while(!(line = br.readLine()).equals("0")) {
            
            // 입력
            String[] arrStrNum = line.split(" ");
            int[] arrNum = new int[Integer.parseInt(arrStrNum[0])];
            for (int i = 0; i < arrNum.length; i++) {
                arrNum[i] = Integer.parseInt(arrStrNum[i + 1]);
            }
            
            listLotto = new ArrayList<Integer>();
            listCompleteLotto = new ArrayList<String>();
            
            // 재귀함수 실행
            go(arrNum, 0, 0);
            
            //출력
            for (int i = 0; i < listCompleteLotto.size(); i++) {
                bw.write(listCompleteLotto.get(i) + "\n");
            }
            bw.write("\n");
            bw.flush();
        }
    }
    
    private static void go(int[] arrNum, int index, int cnt) {
 
        // 6자리 완성됐을 때
        if (cnt == 6) {
            StringBuilder sb = new StringBuilder();
            for (int i = 0; i < listLotto.size(); i++) {
                sb.append(listLotto.get(i));
                sb.append(" ");
            }
            listCompleteLotto.add(sb.toString());
            return;
        }
        // 추가가 불가능한 경우
        if (index == arrNum.length) {
            return;
        }
        
        // 한자리 추가
        listLotto.add(arrNum[index]);
        go(arrNum, index + 1, cnt + 1);
        // 한자리 제거
        listLotto.remove(listLotto.size() - 1);
        go(arrNum, index + 1, cnt);
    }
}

 

 

TIP1 - 방법1

next_permutation, prev_permutation은 각기 전체 수열의 사전순/역사전순 순열이기 때문에

1111000 과 같이, 숫자가 중복된 수열도 순열을 만들 수 있다. 

이를 응용하여 숫자를 포함 여부를 결정할 수 있다!

 

 

TIP2 - 방법 2

백트랙킹 기법을 사용할 때에는 종료조건을 특히 신경쓰자

종료조건이 1가지가 아닐 수 있다.