백준 / 15649 / N과 M(1) / C++

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

15649번: N과 M (1)

N과 M (1) 

 

문제

자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.

• 1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열

입력

첫째 줄에 자연수 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 8)

 

출력

한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다.

수열은 사전 순으로 증가하는 순서로 출력해야 한다.

 

풀이

 

 

대표적인 백트래킹 문제입니다. 주어지는 N개의 자연수 중에서 중복 없이 M개를 고르는데, 순서가 다르면 서로 다른 Case로 판단하는 순열입니다. [1 2]와[2 1]은 서로 다른 수열로 취급하고있죠.

 

결국 만들 수 있는 모든 경우의 수를 다 탐색해봐야 하기 때문에 DFS를 사용해서 구현했습니다. 그런데 전혀 예상하지 못한 시간초과를 만났습니다. N과 M 모두 입력 최댓값이 8이기 때문에 시간초과가 날 이유가 없다고 생각했기 때문에 당황했습니다. 벡터 또한 push_back과 pop_back만 사용했기 때문에 그로 인한 시간초과는 아닐거라 생각했습니다. 

 

백준 사이트 질문게시판을 통해 같은 이유로 올라온 질문을 통해 해결하게 되었습니다. 문제는 endl 이었습니다 !

예전에 한창 백준에서 문제풀이를 할 때도 endl을 사용하면 시간초과가 나고 \n을 사용하면 시간초과가 나지 않는 문제들이 있었는데, 이번 문제 역시 endl을 \n으로 바꾸니 시간초과 문제가 깔끔히 해결되었습니다.