백준 6603 로또 / C++

문제 : 링크텍스트

풀이 point

주어진 수를 활용하여 6개의 순열 조합을 구해야함
오름차순 기준, 중복 허용 x

• 백트래킹, 재귀를 활용

풀이 순서

1. 입력 받기

• k를 입력받고, k만큼 정수를 입력받아 벡터에 저장
• k가 0이면 입력 종료

2. solve 함수 구현

• 6개의 조합이 완성 됐다면 출력
• 6개 조합을 위해 입력 받은 nums 배열에서 조합 생성
• 오름차순 + 중복허용 x 이기 때문에 현재 인덱스보다 작은 인덱스의 값들은 필요x
• visit 배열은 위에 이유 때문에 필요x
• 대신 for문의 초기값을 그 이전 인덱스를 보지 않도록 설정
• 초기화 필요x,
  nums, result 모두 이전 값에 덮어쓰기 되고, nums의 경우 for문에서 k까지 제한이 되어있기 때문에 그 전에 최대 12 길이 배열이 들어와도 문제x

코드

//백준 1260, DFS와 BFS

#include <iostream>
#include <vector>

int K;
std::vector<int> nums(12, 0);
std::vector<int> result(6);

void solve(int start, int cnt){
    if(cnt == 6){
        for(auto n : result) std::cout << n << ' ';
        std::cout << '\n';
        return;
    }
    for(int i = start; i < K; ++i){
        result[cnt] = nums[i];
        solve(i + 1, cnt + 1);
    }
}

int main(){
    while(true){
        std::cin >> K;
        if(K == 0) break;
        for(int i = 0; i < K; ++i){
            std::cin >> nums[i];
        }
        
        solve(0, 0);
        std::cout << '\n';
    }
    return 0;
}