[ BOJ / 파이썬 ] 15652 N과 M(4)

|  제출 1  |

# 백트래킹으로 구현
import sys
input = sys.stdin.readline
n,m = map(int, input().split())

group = []
result = []
def find():

  if len(group) == m:
    if not sorted(group) in result:
      result.append(sorted(group))
    return

  for i in range(1, n+1):
      group.append(i)
      find()
      group.pop()

find()

for r in result:
  print(' '.join(list(map(str, r))))

 

: 역시 사람은 겸손해야한다는 것을 느끼게 된 문제였다.

: 이전 문제랑 답이 같은데? 뭐 고칠것 있나 해서 그냥 냈는데 출력 보면 앞의 어떤 N과M문제와도 답이 같지 않다는 것을 알 수 있다. 

 

 

 

해서 문제를 다시 보면, 앞의 숫자는 1234 차례로 증가하고, 뒤의 숫자는 자기 자신을 최소로 갖는 것을 알 수 있다.

 

1, 2, 3, 4 증가는 큰 범위에서의 for문일테고, 안으로 들어가면 본인 기준으로 재귀가 도는 걸테니까,

 

이전 N과 M 1), 2), 3) 과 다르게 이번 문제에서는 재귀함수 자체에 파라미터를 둬서 함수 도는 구성을 변하게 해야할 필요가 있다. 

 

그래서 고친 게 하단의 코드이다. 

 

|  제출 2  |

import sys
input = sys.stdin.readline
n,m = map(int, input().split())

group = []
result = []
def find(k):

  if len(group) == m:
    print(' '.join(list(map(str,group))))
    return

  for i in range(k, n+1):
      group.append(i)
      find(i)
      group.pop()

find(1)

: 각 숫자마다 for문이 돌면, 자기 자신을 기준으로 for문이 돌아갈 수 있게 했다. 그걸 위해 재귀함수에는 매번 값을 업데이트시켜 들어간다. 

 

: 같은 수를 여러번 골라도 된다고 했으니 바로 출력해주는 것도 가능했다.