문제 정보
https://www.acmicpc.net/problem/15652
문제
자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.
- 1부터 N까지 자연수 중에서 M개를 고른 수열
- 같은 수를 여러 번 골라도 된다.
- 고른 수열은 비내림차순이어야 한다.
- 길이가 K인 수열 A가 A1 ≤ A2 ≤ ... ≤ AK-1 ≤ AK를 만족하면, 비내림차순이라고 한다.
입력
첫째 줄에 자연수 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 8)
출력
한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다.
수열은 사전 순으로 증가하는 순서로 출력해야 한다.
접근방법
1. 중복값을 어떻게 처리해야할까?
출력 결과를 잘 보면 기준점(왼쪽) 숫자는 본인과 같은 숫자, 본인보다 큰 숫자를 오른쪽에 둘 수 있다.
그럼 기준점이 커지면 어떻게 될까? 기준숫자보다 작은 숫자는 오른쪽에 오지 못한다.
그럼 어떻게 해결할 수 있을까?? idx 값을 사용해서 하나씩 증가시켜 줄 것이지만 증가시켜주는 위치가 중요할 것 같다.
풀이
def BT(idx):
if len(dap) == M:
print(*dap)
return
else:
while idx != N:
num = nums[idx]
dap.append(num)
BT(idx)
idx += 1
dap.pop()
pass
N, M = map(int, input().split())
nums = [1 + i for i in range(N)]
idx = 0
dap = []
BT(idx)
이전과는 달리 BT 함수를 호출하면서 idx 값을 증가시켜주지 않는다.
그 이유는 같은 값을 가지는 중복이 허용되기 때문이다.
dap 에 1을 넣고 다시 1을 넣기 위해 idx 값을 증가시켜주지 않고 함수를 호출하고
if 조건을 만족하면 함수를 호출한 위치로 리턴해준 뒤 idx 의 값을 증가시킨다.
이렇게 하면 기준값을 1로 할 수 있는 모든 경우의 수를 체크한 뒤 다시 함수 호출 위치로 돌아와서
idx 값을 1 증가시켜준다.
느낀점
N과M을 4까지 풀다보니 가지치기를 연습하기 위한 문제처럼 느껴졌다.
백 트래킹에 대해서 아주 살짝 더 이해한 것 같아서 기분이 좋고
백트래킹을 활용한 다른 문제들도 몇개 풀어봐야겠다.
'컴퓨터 > Algorithm' 카테고리의 다른 글
백준 17298 오큰수 (파이썬) (0) | 2022.09.12 |
---|---|
백준 1759 암호 만들기 (파이썬) (0) | 2022.09.09 |
백준 15649 N과 M (2) (파이썬) (0) | 2022.09.06 |
백준 15649 N과 M (1) (파이썬) (0) | 2022.09.05 |
백준 2667 단지번호붙이기(파이썬) (0) | 2022.09.04 |