[BOJ/PYTHON] 15665. N과 M (11), 15666. N과 M (12)

백준 문제 링크: https://www.acmicpc.net/problem/15665

문제 요약

N개의 자연수 중에서 M개를 고른 수열

수열은 사전 순으로 증가하는 순서로 출력

같은 수를 여러 번 골라도 된다.

중복되는 수열을 여러 번 출력하면 안됨

핵심 아이디어

9번 문제 풀이에서 if i not in array 를 지워줬다.

풀이

# silver3-15665. N과 M (11)

import sys
input = sys.stdin.readline

n, m = map(int, input().split())
nums = list(map(int, input().split()))

nums.sort()
array = []

def back():
    if len(array) == m:
        for i in array:
            print(nums[i], end=' ')
        print()
        return
    last_num = 0
    for i in range(n): # 인덱스        
        if nums[i] != last_num:
            array.append(i)
            last_num = nums[i]
            back()
            array.pop()

back()

실행 시간

메모리 31256KB, 시간 31256ms (python3)

 

 

 

 

 

---

 

 

 

백준 문제 링크: https://www.acmicpc.net/problem/15666

문제 요약

N개의 자연수 중에서 M개를 고른 수열

수열은 사전 순으로 증가하는 순서로 출력

고른 수열은 비내림차순이어야 한다.

중복되는 수열을 여러 번 출력하면 안됨

고른 수열은 비내림차순

핵심 아이디어

10번 풀이에서 if i not in array를 지워줬다.

풀이

# silver3-15666. N과 M (12)

import sys
input = sys.stdin.readline

# N개의 자연수 중에서 M개를 고른 수열
# 수열은 사전 순으로 증가하는 순서로 출력
# 같은 수를 여러 번 골라도 된다.
# 중복되는 수열을 여러 번 출력하면 안됨
# 고른 수열은 비내림차순

n, m = map(int, input().split())
nums = list(map(int, input().split()))

nums.sort()
array = []

def back(idx):
    if len(array) == m:
        for i in array:
            print(nums[i], end=' ')
        print()
        return
    last_num = 0
    for i in range(idx, n): 
        if nums[i] != last_num:
            array.append(i)
            last_num = nums[i]
            back(i)
            array.pop()

back(0)

실행 시간

메모리 31256KB, 시간 52ms (python3)