(파이썬) 백준 알고리즘 - 15649번

N과 M (1)

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

15649번: N과 M (1)

재귀함수를 만들어야되나 생각했는데 코드를 작성하다보니 다른 방법으로 함수를 만들었다.

N, M = map(int, input().split())
 
def add_number():                       # 중복되지 않은 수들로 수열을 만드는 함수
    global result                       # 전역변수에 저장된 값 가져옴
    add = []                            # 새롭게 만들어진 수열
    for re in result:                   # 기존에 있는 수열 중 하나 고름
        for i in range(1, N+1):
            if i in re:                 # 중복되는지 확인
                continue
            else:
                add.append(re + [i])    # 중복되지 않는 경우 새롭게 만들어진 수열을 add에 추가
    result = add                        # 전역변수 result에 새로운 수열을 저장함
 
result = [[i] for i in range(1, N+1)]   # 크기가 1인 수열부터 만듦
while M > 1:                            # M-1번 반복한다
    add_number()
    M -= 1
 
for re in result:                       # 결과 출력
    for r in re:
        print(r, end=' ')
    print()

처음 result라는 배열에 1부터 N까지 수를 하나씩 집어넣는다

result = [[i] for i in range(1, N+1)] # N = 4인 경우
# [[1], [2], [3], [4]]

add_number함수에서는 result에서 하나씩 꺼내서 1부터 N까지의 수 중에 중복되지 않은 수를 붙인 배열을 만든다

add_number() 를 한 번 더 진행하면, 3개의 수를 가진 배열들이 result에 저장된다.

이와 같이 add_number()를 M-1번 수행하면 M개의 수를 가진 수열들을 구할 수 있다.(while M > 1)

 

 

재귀함수를 사용하는 경우는 아래와 같이 작성할 수 있다.

(출처: https://jiwon-coding.tistory.com/21)

n,m = list(map(int,input().split()))
 
s = []
 
def dfs():
    if len(s)==m:
        print(' '.join(map(str,s)))
        return
    
    for i in range(1,n+1):
        if i not in s:
            s.append(i)
            dfs()
            s.pop()
 
dfs()

위와 같은 코드에서 s는 길이가 m이 되면 화면에 출력하고 pop()으로 맨 마지막에 넣은 수가 삭제되어 새로운 배열을 만든다.

n = 4, m = 2인 경우 s의 변화

[1] -> [1,2] 출력 / 2 제거 -> [1] -> [1, 3] 출력 / 3제거 -> [1] -> [1, 4] 출력 / 4제거 -> [1] 제거 -> []

for에서 i = 2로 다시 위와 같이 반복한다.

 

 

 

참고한 페이지

https://jiwon-coding.tistory.com/21

[백준] 15649번 N과 M(1) / 파이썬(python)