15649_N과M(1)

문제는 더보기!

 

문제

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

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

  입력

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

  출력

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

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

  예제 입력 1 복사

  3 1
  

  예제 출력 1 복사

  1
  2
  3
  

  예제 입력 2 복사

  4 2
  

  예제 출력 2 복사

  1 2
  1 3
  1 4
  2 1
  2 3
  2 4
  3 1
  3 2
  3 4
  4 1
  4 2
  4 3
  

  예제 입력 3 복사

  4 4
  

  예제 출력 3 복사

  1 2 3 4
  1 2 4 3
  1 3 2 4
  1 3 4 2
  1 4 2 3
  1 4 3 2
  2 1 3 4
  2 1 4 3
  2 3 1 4
  2 3 4 1
  2 4 1 3
  2 4 3 1
  3 1 2 4
  3 1 4 2
  3 2 1 4
  3 2 4 1
  3 4 1 2
  3 4 2 1
  4 1 2 3
  4 1 3 2
  4 2 1 3
  4 2 3 1
  4 3 1 2
  4 3 2 1​

처음에는 단순히 모든 경우의 수를 출력 한후에, 중복된 값을 제거하면 될줄 알았다. for문을 겹치게 사용되는 방식이라 재귀함수를 써야하나? 라는 생각도 들긴 했는데 우선 while문으로 구현해도 될 것 같아 구현을 해봤다.

리스트를 하나 만든 후에, [1,1,1,1] [1,1,1,2] 이런식으로 숫자를 바꿔나가는 방법이었다.

 

N,M = map(int,input().split())

lst=[1] * M
index = -1
flag = 0

while( lst[0] <= N ):
    if len(set(lst)) == len(lst):
        print(' '.join(map(str,lst)))

    while ( lst[index] == N and index != -M ):
        lst[index]=1
        index -= 1
        flag = 1

    lst[index] += 1

    if flag:
        index = -1
        flag = 0

동작은 정상 작동하지만, 여지없이 시간초과가 떠버렸다. 뭔가 예상가기도 했고 코드를 상당히 c언어처럼 짜서 마음에 들지도 않았다.. 결국 맨처음에 딱 보았던 재귀함수가 떠올랐는데 이 문제가 백트래킹인것을 보고 우선 백트래킹이 무엇인지 공부를 조금 하였다.

 

오래걸리지는 않았고, 결국 백트래킹이란 조건이 부합되지 않으면 도망가는 DFS 즉, 경우 전체를 확인하는 방법이다. 원래 방법에서 확인하는 과정에서 분명 문제가 나는 것이라 생각했다. 그래서 방법을 바꾸어 생각해보았다.

 

스택을 하나 만든 후에, 숫자를 계속채워나가는 방식이다.

 

N,M = map(int,input().split())

lst=[]

def f():
    if len(lst) == M:
        print(' '.join(map(str,lst)))
        return

    for i in range(1,N+1):
        if i not in lst:
            lst.append(i)
            f()
            lst.pop()

f()

 

입력이 4 2 라고생각하면

[ 1 ]    >  [1 , 2 ]  > [ 1 ] > [ 1, 3 ]  > [ 1 ] 이런식으로 나갔다 들어갔다하는 식으로 쌓이게 하는것이다.

 

확실히 for문이 변수대로 쌓여가는 형식들은 재귀함수가 훨씬 효율적인 것 같다..