[백준] 15651-15652. N과 M(3)-(4) 파이썬

2020/03/02 - [파이썬 코딩테스트/BAEK JOON] - [백준] 15649. N과 M (1) 파이썬

2020/03/02 - [파이썬 코딩테스트/BAEK JOON] - [백준] 15650 N과 M(2) 파이썬

 

---

* DFS 재귀방식을 이용한 파이썬 풀이입니다.

문제출처 https://www.acmicpc.net/problem/15651

---

[백준] 15651 N과 M(3) 파이썬

문제

자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.

• 1부터 N까지 자연수 중에서 M개를 고른 수열

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

입력

첫째 줄에 자연수 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 7)

출력

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

수열은 사전 순으로 증가하는 순서로 출력해야 한다.

---

<풀이>

# 3번. [백준] 15651
# 1~n 중에 m 개 뽑기. 중복사용가능. 순서있음. [1,2],[2,1] 다르게 봄
n,m = map(int,input().split())
numbers = [i+1 for i in range(n)] # 1~n까지
is_number = [0 for _ in range(m)] # 출력 개수
#check = [False for _ in range(n)] # 사용여부 필요없음
def dfs(idx):
    if idx >= m: # 0부터 m출력개수 되면
        print(*is_number)
        return
    for i in range(n):
        is_number[idx] = numbers[i]
        dfs(idx+1)
 
dfs(0)
 

중복을 허용하므로, 사용여부를 체크할 필요가 없어짐

n,m = 4,2 일 때

 

 

---

---

문제출처 https://www.acmicpc.net/problem/15652

---

[백준] 15652 N과 M(4) 파이썬

문제

자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.

• 1부터 N까지 자연수 중에서 M개를 고른 수열

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

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

  • 길이가 K인 수열 A가 A1 ≤ A2 ≤ ... ≤ AK-1 ≤ AK를 만족하면, 비내림차순이라고 한다.

입력

첫째 줄에 자연수 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 8)

출력

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

수열은 사전 순으로 증가하는 순서로 출력해야 한다.

---

<풀이>

# 4번. [백준] 15652 (1)
# 1~n 중에 m 개 뽑기. 중복사용가능. 순서없음. [1,2]=[2,1] 같게 봄
n,m = map(int,input().split())
numbers = [i+1 for i in range(n)] # 1~n까지
is_number = [0 for _ in range(m)] # 출력 개수
#check = [False for _ in range(n)] # 사용여부 필요없음
def dfs(idx,next):
    if idx >= m: # 0부터 m출력개수 되면
        print(*is_number)
        return
    for i in range(next,n):
        is_number[idx] = numbers[i]
        dfs(idx+1,i) # 재귀포문에선 처음부터 아닌 나부터~
dfs(0,0)
 
 

뽑는건 중복을 허용하지만, 배치는 중복을 허용하지 않고, 오름차순으로 나와야 한다.

길이가 K인 수열 A가 A1 ≤ A2 ≤ ... ≤ AK-1 ≤ AK를 만족하면, 비내림차순

15651 N과 M(3) 에서 13번째 줄, dfs(idx+1,i) 만 변경 # 재귀포문에선 처음부터 아닌 나부터~

 

n,m = 4,2

<그냥 해본 연습>

어, 그럼 아까 삼번 문제는 결과값을 다 허용했는데 여기서는 같은 배치요소들이면 오름만 가능하니깐

8번째 줄의, 출력시 제한을 걸어볼까? 생각도 하긴했다. ㅋㅋㅋㅋ  쓸데없는 것도 다 돌면서 또 비교하는 ㅋㅋㅋ

문제 출제의도가 이건 아니겠지 

# 4번. [백준] 15652 (2)
# 1~n 중에 m 개 뽑기. 중복사용가능. 순서없음. [1,2]=[2,1] 같게 봄
n,m = map(int,input().split())
numbers = [i+1 for i in range(n)] # 1~n까지
is_number = [0 for _ in range(m)] # 출력 개수
#check = [False for _ in range(n)] # 사용여부 필요없음
def dfs(idx,next):
    if idx >= m: # 0부터 m출력개수 되면
        cnt = 1
        for x in range(len(is_number)-1):
            if is_number[x] > is_number[x]:
                cnt = 0 
        if cnt:
            print(*is_number)
        return
    for i in range(next,n):
        is_number[idx] = numbers[i]
        dfs(idx+1,next)
dfs(0,0)