Be a developer

이전에 풀었던 로또 문제를 재귀로 푸는 것이다. 이전에는 순열로 풀기위해 선택한 번호는 0으로 넣고, 선택하지 않은 번호는 1로 넣는 새로운 vector를 선언해주었다. 하지만 재귀에서는 앞선 암호 문제처럼 재귀를 통해 넣고, 안 넣고를 할 수 있기 때문에 새로운 vector가 필요없다. 대신 넣고 안 넣고를 check할 check 배열을 하나 생성한다. check 배열을 놓고 풀지 않고, vector하나를 두고 선택하면 vector에 push_back으로 넣고, 넣지 않으면 pop_back으로 빼서 풀 수도 있다. 자세한 설명은 아래 주석으로.. 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484..

이 문제는 배열 안에 중복된 수가 있어도 next_permutation이 잘 작동한다는 것을 이용해서 푼다. 예시와 같이 k=8, s={1,2,3,5,8,13,21,34}인 경우 0을 먼저 6개 넣고, 다음에 1을 2개 넣어야 한다. 그렇게 되면 0 0 0 0 0 0 1 1과 같은 vector가 만들어지고, 이를 next_permutation을 사용해 섞으면 뒤에서 부터 섞이게 되어 모든 순열을 다 검사할 수 있다. 만약 1을 6개 먼저 넣고 0을 2개 넣게 되면, 1 1 1 1 1 1 0 0 과 같은 vector가 만들어지고, 모든 순열을 다 검사하지 못하게 된다. 원소는 오름차순으로 입력받기 때문에 sorting할 필요가 없다. 0과 1을 vector에 넣을 때 조심해야 한다. vector v(n)과..