0302_백준 15656~15666번 : N과M문제 (재귀함수로 순열, 조합 구하기)part2

출처 : 백준 15656번 문제~

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

15663번: N과 M (9)

어제에 이어 오늘 재귀함수로 구하는 순열, 조합 N과M 문제를 마무리 ..!

어제보다 난이도가 살짝 높았지만.. 주변 블로거님들 참고하며 극복ㅎㅎ

 

이전 문제들은 비슷한 맥락이지만, N과M 문제 9번부터 N개의 자연수 중 중복되는 숫자가 있어 이를 처리해줘야 하는 부분에서 조금 헤맸다. 해결방법은 overlap 이라는 새로운 변수를 만들어 만든 부분집합의 값을 저장, 해당 값이 이미 만들어져 있지 않으면 이프문을 실행해 재귀로 부분집합을 구해내는 것이다. 9번부터 12번까지는 모두 이 방법을 동일하게 적용시켜 풀 수 있는 문제들이다.

 

N과M문제를 연달아 풀면서 재귀함수의 아웃라인을 조금 만들 줄 알게 됐다. 며칠 지나고 한층 어려운 재귀함수 문제를 추가적으로 풀어볼 예정이다. 그럼 오늘은 여기까지.

 

# 15656번

# 중복 가능, 중복 추출 가능
def p(k, n, m):
    if (k == m):
        print(*res)
        return
    else:
        for i in range(n):
            visited[i] = 1
            res[k] = arr[i]
            p(k+1, n, m)
            visited[i] = 0
 
n, m = map(int,input().split())
arr = sorted(list(map(int,input().split())))
res = [0] * m
visited = [0 for i in range(n)]
p(0,n,m)

# 15657번

# 중복 수열 불가, 중복 추출 가능
def c(k, n, m, l):
    if(k==m):
        print(*res)
        return
    else:
        for i in range(n):
            if arr[i] >= l:
                visited[i] = 1
                l = arr[i]
                res[k] = arr[i]
                c(k+1,n,m,l)
                visited[i] = 0
 
n, m = map(int, input().split())
arr = sorted(list(map(int, input().split())))
res = [0] * m
visited = [0 for i in range(n)]
c(0,n,m,0)

# 15663번

# 순열, 중복추출 불가
def p(k, n, m):
    if(k==m):
        print(*res)
        return
 
    overlap = 0
    for i in range(n):
        if not visited[i] and overlap != arr[i]:
            visited[i] = 1
            res[k] = arr[i]
            overlap = arr[i]
            p(k+1, n, m)
            # 재귀 끝나고 초기화
            visited[i] = 0
 
n, m = map(int,input().split())
arr = sorted(list(map(int, input().split())))
res = [0] * m
visited = [0 for i in range(n)]
p(0, n, m)

# 15664번

# 조합 #N개 중 동일한 자연수 있음
def c(k,n,m,l):
    if (k==m):
        print(*res)
        return
 
    overlap = 0
    for i in range(n):
        if not visited[i] and overlap != arr[i] and arr[i] >= l:
            visited[i] = 1
            res[k] = arr[i]
            l = arr[i]
            overlap = arr[i]
            c(k+1, n, m, l)
            visited[i] = 0
 
n, m = map(int,input().split())
arr = sorted(list(map(int,input().split())))
res = [0] * m
visited = [0 for i in range(n)]
c(0,n,m,0)

# 15665번

# 순열 #겹치는 자연수 있음
def p(k,n,m):
    if (k==m):
        print(*res)
        return
    overlap = 0
    for i in range(n):
        if overlap != arr[i]:
            visited[i] = True
            overlap = arr[i]
            res[k] = arr[i]
            p(k+1,n,m)
            visited[i] = False
 
n, m = map(int,input().split())
arr = sorted(list(map(int,input().split())))
res = [0] * m
visited = [0 for i in range(n)]
p(0,n,m)

# 15666번

# 조합 # 중복 자연수 존재
def c(k,n,m,l):
    if (k ==m):
        print(*res)
        return
    overlap = 0
    for i in range(n):
        if overlap != arr[i] and arr[i] >= l:
            visited[i] = 1
            overlap = arr[i]
            l = arr[i]
            res[k] = arr[i]
            c(k+1,n,m,l)
            visited[i] = 0
 
n, m = map(int,input().split())
arr = sorted(list(map(int,input().split())))
res = [0] * m
visited = [0 for i in range(n)]
c(0,n,m,0)