티스토리 뷰

알고리즘/백준

15664번 N과M(10) 백준

글을 쓰는 개발자 2020. 12. 6. 19:41
반응형

문제:www.acmicpc.net/problem/15664

 

15664번: N과 M (10)

한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해

www.acmicpc.net

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
import sys
N,M = map(int,sys.stdin.readline().split())
li=[int(i) for i in sys.stdin.readline().split()]
check=[0]*10001
passing=[0]*10001
init=[False]*10001
for i in li:
    check[i]+=1
dic = set(li)
li=list(dic)
li.sort()
ans=[]
 
def func(celi):
    if celi==M:
        print(' '.join(ans))
        return
    for i in range(len(li)):
        if not ans:
            if init[li[i]]!=True:
                init[li[i]]=True
                passing[li[i]]=1
                ans.append(str(li[i]))
                func(celi+1)
                passing[li[i]]=0
                ans.pop()
        else:
            if passing[li[i]]<check[li[i]] and int(ans[-1])<=li[i]:
                passing[li[i]]+=1
                ans.append(str(li[i]))
                func(celi+1)
                passing[li[i]]-=1
                ans.pop()
 
func(0)
cs

이 문제는 N과M(9)에서 28번째 줄을 추가했다. (대소관계만 추가!)

 

다른 분들은 어떻게 풀었나 보니 라이브러리로 푸는 분이 있어서 올린다.

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
from itertools import combinations
 
N, M = map(int, input().split())
N_list = list(map(int, input().split()))
N_list = sorted(N_list) #순서대로 나오게 정렬 먼저
output = [] #중복 제거하기 위한 리스트 생성
 
for numbers in list(combinations(N_list, M)):
    if not output:
        output.append(numbers)
    elif numbers not in output: # 중복 제거
        output.append(numbers)
            
for numbers in output:
    for num in numbers:
        print(num, end=' ')
    print()
cs

참고:https://claude-u.tistory.com/308

 

#257 백준 파이썬 [15664] N과 M (10) - 조합

https://www.acmicpc.net/problem/15664 Python Code from itertools import combinations N, M = map(int, input().split()) N_list = list(map(int, input().split())) N_list = sorted(N_list) #순서대로 나오..

claude-u.tistory.com

combinations라는 라이브러리를 이용하여 해결하였다.

반응형

'알고리즘 > 백준' 카테고리의 다른 글

외판원 순회2 10971번 백준 파이썬  (0) 2020.12.07
10972번 다음 순열 백준  (0) 2020.12.06
15663번 N과M(9) 백준  (0) 2020.12.06
1107번 리모컨 백준  (0) 2020.12.05
RGB거리2 17404번 백준  (0) 2020.12.04
반응형
공지사항
최근에 올라온 글
최근에 달린 댓글
Total
Today
Yesterday
링크
«   2024/12   »
1 2 3 4 5 6 7
8 9 10 11 12 13 14
15 16 17 18 19 20 21
22 23 24 25 26 27 28
29 30 31
글 보관함