백준 6603 로또 c++, Kotlin (조합) 22.06.13 Kotlin 추가

문제 출처 : www.acmicpc.net/problem/6603

6603번: 로또

문제

독일 로또는 {1, 2, ..., 49}에서 수 6개를 고른다.

로또 번호를 선택하는데 사용되는 가장 유명한 전략은 49가지 수 중 k(k>6)개의 수를 골라 집합 S를 만든 다음 그 수만 가지고 번호를 선택하는 것이다.

예를 들어, k=8, S={1,2,3,5,8,13,21,34}인 경우 이 집합 S에서 수를 고를 수 있는 경우의 수는 총 28가지이다. ([1,2,3,5,8,13], [1,2,3,5,8,21], [1,2,3,5,8,34], [1,2,3,5,13,21], ..., [3,5,8,13,21,34])

집합 S와 k가 주어졌을 때, 수를 고르는 모든 방법을 구하는 프로그램을 작성하시오.

입력

입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있다. 첫 번째 수는 k (6 < k < 13)이고, 다음 k개 수는 집합 S에 포함되는 수이다. S의 원소는 오름차순으로 주어진다.

입력의 마지막 줄에는 0이 하나 주어진다. 

출력

각 테스트 케이스마다 수를 고르는 모든 방법을 출력한다. 이때, 사전 순으로 출력한다.

각 테스트 케이스 사이에는 빈 줄을 하나 출력한다.

알고리즘 분류

 

• 수학
• 조합론
• 백트래킹
• 재귀

풀이

조합 문제이다.

dfs로 k개의 수를 완전탐색하면서, 뽑은 숫자의 수가 6개의 배열로 만들어질 때 dfs를 탈출하고, 출력한다.

굳이 vector로 안 해도 된다.

2022.06.13 코틀린 코드 추가

코드1(c++)

#include<iostream>
#include<vector>
using namespace std;

int ans[6];
int n = 1;

void dfs(vector<int> v, int start, int depth) {

    if (depth == 6) {
        for (int i = 0; i < 6; i++) {
            cout << ans[i] << ' ';
        }
        cout << '\n';
    }
    for (int i = start; i < n; i++) {
        ans[depth] = v[i];
        dfs(v, i+1, depth+1);
    }


}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);



    while (n) {
        cin >> n;
        vector<int> v(n);
        for (int i = 0; i < n; i++) {
            cin >> v.at(i);
        }

        dfs(v,0,0);
        cout << '\n';
    }

    return 0;
}

코드2(Kotlin)

import java.util.*
val br = System.`in`.bufferedReader()
val bw = System.out.bufferedWriter()

fun combination(input: List<Int>, len: Int,idx: Int, n: Int, result: IntArray ){
    if(len==6){
        for(r in result){
            bw.write("$r ")
        }
        bw.write("\n")
        return
    }
    for(i in idx until n){
        result[len] = input[i]
        combination(input, len+1, i+1, n, result)
    }
}

fun main(){

    while(true){
        //input
        val tk = StringTokenizer(br.readLine())
        val n = tk.nextToken().toInt()
        if(n==0) break
        val input = List(n){tk.nextToken().toInt()}
        //solve
        combination(input,0,0, n, IntArray(6))
        bw.write("\n")
    }
    bw.close()
}