[Python] 백준 15650 N과 M (2)

 

문제 분석

• 1~n까지 자연수 중 중복 없이 m개를 고른 수열
• 고른 수열은 오름차순 : 순서가 없음
• 조합

 

코드 설계

• 수열에 넣을 ans = [ ]
• 종료조건 : len(arr) == m
• 고른 수열이 오름차순이 되도록 어떻게?
• ans에 없으면 넣을 건데,
• i가 현재 넣을까? 하는 수
• 만약 i가 j(ans)에 들어있는 수 보다 작으면 continue (오름차순)
• 작으면 append - dfs - pop

 

정답 코드

1차 - 틀림

import sys
input = sys.stdin.readline

n,m = list(map(int, input().split()))
ans = []

def dfs():
    if len(ans) == m :
        print(' '.join(map(str, ans)))
        return

    for i in range(1, n+1):
        if i not in ans: # 중복x
            if len(ans) > 0 : # ans가 비어있지 않다면
                for j in ans:
                    if i <= j : # 이미 들어있는 수가 더 크면 continue
                        continue
                    else :
                        ans.append(i)
                        dfs()
                        ans.pop()
            else : # 비어있다면
                ans.append(i)
                dfs()
                ans.pop()

dfs()

넣고 i가 증가 안해서 1을 넣고 다시 dfs( )

 

2차

import sys
input = sys.stdin.readline

n,m = list(map(int, input().split()))
ans = []

def dfs(start):
    if len(ans) == m :
        print(' '.join(map(str, ans)))
        return

    for i in range(start, n+1):
        if i not in ans: # 중복x
            ans.append(i)
            dfs(i+1)
            ans.pop()

dfs(1)

..

itertools

import sys
from itertools import combinations

input = sys.stdin.readline

n, m = map(int, input().split())
arr = [ i for i in range(1,n+1) ]

for i in combinations(arr, m) : 
    for j in i : 
       print(j, end = ' ')
    print()