[코딩테스트] 백준 N과 M (2) 파이썬(Python)

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

15650번: N과 M (2)

n,m = map(int, input().split())

result = []
k = 1
def solve(k):
  if len(result) == m:
    print(' '.join(map(str, result)))
    return
  for i in range(k, n+1):
    if i not in result:
      result.append(i)
      solve(i+1)
      result.pop()
    
solve(k)

N과 M (1) 문제와 마찬가지로 두가지 방법을 통하여 문제를 해결하였습니다.

문제의 특징으로는 조합(combinations)을 구하여 출력하는 것입니다.

또한 인덱스의 수가 작을 수록 즉 앞부분에 위치한 수가 뒷부분에 위치한 수보다 작다라는 특징이 있습니다.

위의 출력처럼 1 < 2, 1 < 3, 1 < 4 .. 의 특징을 가지고 있습니다.

 

N과 M (1) 문제의 코드를 참고했지만 solve에 전달하는 인자값을 추가하여 문제를 해결하였습니다.

N과 M (1) 문제 풀이는 아래의 링크를 참고 하시면 됩니다.

[코딩테스트] 백준 N과 M (1) 파이썬(Python)

k = 1로 시작하여 i가 1부터 시작하게 만들고 result에도 1이 들어가 있는 것을 확인할 수 있습니다.

다음은 solve로 전달하는 인자값을 i + 1을 전달합니다.

호출되는 재귀함수 solve()의 반복문의 시작을  i+1을 하게 만듭니다.

이렇게 함수를 진행하게 되면 result에 들어가는 값들은 앞부분의 값들보다는 큰 값들이 들어가게 됩니다.

from itertools import combinations
n,m = map(int, input().split())
array = [i for i in range(1, n+1)]
for lst in combinations(array, m):
  print(' '.join(map(str, lst)))

두번째 방법은 combinations 라이브러리를 사용하여 문제를 해결하였습니다.

print(list(combinations(array, m)))

아래는 print문의 결과입니다. 보이는 것처럼 조합의 모든 경우의 수를 출력한것을 확인할 수 있습니다.