0301_3월 첫 날/백준 15649 ~ 15655번 : N과M문제 (재귀함수로 순열, 조합 구하기)

# 출처 : 백준 N과M 문제 

https://www.acmicpc.net/workbook/view/2052

문제집: N과 M (baekjoon)

 

그 동안 순열과 조합을 itertools 외장 라이브러리를 사용하여 순열과 조합을 만들어 왔으나, 재귀함수를 이용해 풀어보는 연습이 꼭 필요하다는 피드백을 받아서 이를 연습하고자 백준 N과 M문제를 풀기 시작했다. 오늘은 6문제 정리하였고, 내일 6문제 추가로 풀 예정이다.

 

아직 함수를 쓰는 것도, 재귀 개념을 활용하는 것도 서툴지만 여러 차례 반복하여 문제를 풀다 보니 차츰 개념이 정리되는 느낌이다. 

 

[풀이 과정 정리]
 
중복 가능 : 순열 P 함수
중복 불가능 : 조합 C 함수

* 고려해야 할 요소 : 구한 수열들의 중복이 가능 유무, 숫자 중복 추출 가능 유무, 수열 오름차순 정렬 유무 등

* 아래 푼 코드 내용 中
- n,m은 입력값
- arr는 답(res)에 넣기 위한 n까지의 숫자 배열
- res 출력 되는 수열 조합들
- visited 중복을 확인 용도

# 15649번 

# 순열하고 조합 만들기 기초
# 여기서는 순열 (중복 가능)
def p(k,n,m):
    if (k == m):
        print(*res)
        return
    else:
        for i in range(n):
            if(visited[i] == 0):
                visited[i] = 1
                res[k] = arr[i]
                p(k+1, n, m)
                visited[i] = 0
 
n, m = map(int,input().split())
arr = range(1, n+1)
res = [0] * m
visited = [0 for i in range(n)]
 
p(0,n,m)

# 15650 번

# 조합 (중복 불가)
def c(k,n,m,l):
    if (k==m):
        print(*res)
        return
    else:
        for i in range(n):
            if (visited[i]==0 and l <arr[i]):
                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 = range(1, n+1)
visited = [0 for i in range(n)]
res = [0] * m
c(0,n,m,0)

# 15651 번

# 순열로
# 같은 수 여러번 뽑기 가능
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 = range(1, n+1)
res = [0] * m
visited = [ 0 for i in range(n)]
p(0,n,m)

# 15652 번

# 조합으로
def c(k,n,m,l):
    if (k == m):
        print(*res)
        return
    else:
        for i in range(n):
            if(l<= arr[i]):
               visited[i] = 1
               l = arr[i]
               res[k] = arr[i]
               c(k+1,n,m,l)
 
n, m = map(int,input().split())
arr = range(1,n+1)
visited = [0 for i in range(n)]
res = [0] * m
c(0,n,m,0)

# 15654 번

# 순열
def p(k,n,m):
    if (k == m):
        print(*res)
        return
    else:
        for i in range(n):
            if visited[i] == 0:
                visited[i] = 1
                res[k] = n_lst[i]
                p(k+1, n, m)
                visited[i] = 0
 
n, m = map(int,input().split())
n_lst = sorted(list(map(int, input().split())))
res = [0] * m
visited = [0 for i in range(n)]
 
p(0,n,m)

# 15655 번

# 중복 불가 : 조합
def c(k,n,m,l):
    if (k == m):
        print(*res)
        return
    else:
        for i in range(n):
            if (visited[i]==0 and arr[i]>l):
                visited[i] = 1
                res[k] = arr[i]
                l = 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)