🥚

Recent Notes

See 20 more →

BOJ - 로또(6603)

3 min read

실버2 : 조합 문제이다.

풀이1

기본적인 조합 문제이다.

Code

import sys
from itertools import combinations
 
input = sys.stdin.readline
 
while True:
    input_list = list(map(int, input().split()))
    if input_list[0] == 0:
        break
    k, s = input_list[0], input_list[1:]
 
    for combi in list(combinations(s, 6)):
        for c in combi:
            print(c, end=" ")
        print()
    print()

풀이2

단순한 문제였다. 재귀를 통해 만들 수 있는 모든 경우를 출력하면 되는 문제였다. 나 같은 경우 재귀를 통해 들어갈 때, 탐색하지 않아도 되는 부분을 거르는 코드를 작성했다. 아마 다른 분들도 작성했을 것이다.

이 문제에서 고려해야 되는 점은 다음과 같다.

  1. 어떻게 출력하게 만들 것인가?
  2. 어느 상황에서 탐색을 하지 않게 가지를 칠 것인가?

출력 방법

checkbox라는 배열을 만들어 깊이가 6이 되었을 때 모두 출력하였다.

백트래킹

이 문제는 간단한 백트레킹이지만, 써보면, 현재 위치에서 나머지 공을 선택할 수 있는 가지수와 지금 부터 선택해야 하는 가지수를 비교했다.

현재 위치로 부터 남은 공의 개수 < 앞으로 선택해야 하는 공의 개수

이와 같은 경우는 탐색이 불가능 하므로 함수를 콜하지 않았다.

Code

// 실버2 : 백준 6603번 로또
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
const int K = 6;
int arr[14];
bool checkbox[14] = {0};
int N = -1;
 
void go(int start, int count){
    int restOfBallFromStart = N-(start+1);
    if (count == 6) {
        for (int i = 0; i < N; i++)
            if (checkbox[i]) cout << arr[i] << " ";
        cout << '\n';
        return;
    }
    for (int i = start+1; i < N; i++) {
        if (restOfBallFromStart < K-(count+1)) break;
        else {
            checkbox[i] = 1;
            go(i, count+1);
            checkbox[i] = 0;
        }
    }
}
 
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    while (N != 0) {
        fill(&arr[0], &arr[13], 0);
        cin >> N;
        for (int i = 0; i < N; i++) {
            cin >> arr[i];
        }
        go(-1, 0);
        cout << '\n';
    }
    return 0;
}

Reference

Graph