[Python] 백준 15649~15652: N과 M

15649 N과 M(1)

def part(k):

    if k==M:
        print(' '.join(map(str,res)))
        return
    else:
        for i in range(1,N+1):
            if not Visited[i]:
                Visited[i] = True
                res.append(i)
                part(k+1)
                Visited[i] = False
                res.pop()

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

Visited = [False] * (N+1)
res =[]
part(0)

 

15650 N과 M(2)

 

1차 시도(성공)

N,M= map(int,input().split())
# 1부터 N까지의 자연수 모임 중 길이가 M인 수열 뽑기
result = []
visit = [False] * (N+1)

def partial(k):
    if k==M:
        # print(result)
        if M>1:
            for i in range(M-1):
                if result[i] > result[i+1]: #사전 순 배열이 아닌 경우
                    return
                # else:
            print(' '.join(map(str,result)))
        else:
            print(' '.join(map(str,result)))
        return
    for i in range(1,N+1):
        if not visit[i]:
            visit[i] = True
            result.append(i)
            partial(k+1)
            visit[i] = False #추후 영향을 주지 않기 위해 원복시킨다.
            result.pop() #추후 영향을~ 원복 2

partial(0)

너무 지저분해서 다시 풀었다.

 

ANS

def find(k):
    if k==M:
        if sorted(res) == res:
            print(' '.join(map(str, res)))
        return
    else:
        for i in range(1,N+1):
            if not visit[i]:
                visit[i] = True
                res.append(i)
                find(k+1)
                res.pop()
                visit[i] = False


N,M = map(int, input().split())
res =[]
visit = [False] * (N+1)
find(0)

 

15651 N과 M(3)

def dfs(k):
    if k==M:
        print(' '.join(map(str, res)))
        return
    else:
        for i in range(1,N+1):
            if not Visited[i]:
                res.append(i)
                dfs(k+1)
                res.pop()

N,M = map(int,input().split())
Visited = [False] * (N+1)
res= []

dfs(0)

15652 N과 M(4)

1차 시도(성공)

N,M = map(int,input().split())
res = []

def dfs(k):
    if k==M:
        if M>1: #조합의 길이가 1 이상인 경우
            if res == sorted(res):
                print(' '.join(map(str, res)))
        else:#(조합의 길이가 1인 경우)
            print(' '.join(map(str, res)))
    else:
        for i in range(1,N+1):
            res.append(i)
            dfs(k+1)
            res.pop()
dfs(0)

시간이 너무 걸려서 같이 스터디 하는 분에게 힌트를 구한 후 범위를 재조절했다. 이 글을 보시진 않겠지만... 좋은 힌트 감사합니다😁 정말 도움이 많이 되었어요......

ANS

def dfs(k):
    if len(res)==M:
        print(' '.join(map(str, res)))
        return
    else:
        for i in range(k,N+1):
            if not visit[i]:
                res.append(i)
                dfs(i)
                res.pop()

N,M = map(int, input().split())
res = []
visit = [False] * (N+1)

dfs(1)