[백준(BOJ)/C++] 6604번: 로또 - 코딩밥상

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

6603번: 로또

 

 

• 접근 방법

문제에서 요구하는것은 k개의 집합 중 로또 번호 6개를 고르는 경우를 모두 나열해서 오름차순으로 출력하는 것이다.

요구하는 바를 보면 k개 중 6개를 선택하는 조합이라는것은 쉽게 알 수 있었다.

c++에서 조합을 구현해본 적은 없기에 헤매고있다가 저번주 스터디 수업에서 배웠던 조합과 순열을 구현할 수 있는stl을 배웠기에 이를 참조하여 문제를 풀었다.

출처: 땅울림 썸머코딩 수업자료

 

 

• 논리 흐름(알고리즘)

핵심은 "next_permutation"함수이다. 내가 이해한대로 이 함수의 기능을 간략하게 설명하자면, 범위 밖의 수가 있을 때 그 수를 포함하여 다음 순열을 구한고 true를 리턴한다.

https://twpower.github.io/82-next_permutation-and-prev_permutation

[Algorithm] C++에서 next_permutation 함수(혹은 prev_permutation 함수)를 통해서 순열 구하기

이 분의 글이 이해하는데에 큰 도움이 되었다. 까먹을때마다 다시 살펴보자.

다시 문제로 돌아가서,

이 순열 함수를 이용하여 조합 또한 구현할 수 있다. 스터디에서 배운것 처럼 주어진 집합 k개 중 6개를 따로 표시하여(0 과 1등으로) 조건에 맞는 수 6개를 구한다면 조합이 되는것이다.

 이 문제에서 조심할 점은 오름차순으로 출력하기때문에 뽑는 수(6개)를 안뽑는 수(k-6개) 보다 작은수로 표시하여

조건문에서 걸러주어 출력해야한다(위에선 0(뽑는 수)과 1(안뽑는 수)로 저장).