문제 정보
https://www.acmicpc.net/problem/15650
문제
자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.
- 1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열
- 고른 수열은 오름차순이어야 한다.
입력
첫째 줄에 자연수 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 8)
출력
한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다.
수열은 사전 순으로 증가하는 순서로 출력해야 한다.
접근방법
1. 중복된 숫자를 무시하는 방법은?
N과M (1)과는 다르게 숫자의 중복을 허용하지 않는다
N과M (1) 에서는 for 문을 이용했지만 그러면 처음~끝 까지 전부 확인한다는 문제가 생긴다.
while문을 사용해서 문제를 해결 해 보자
2. 내가 원하는 숫자를 넣는 방법은?
for 문이 아니라 while 문을 사용해서 중복을 없앨 수 있는 아이디어는 생각했다.
그런데 어떻게 해야 내가 원하는 숫자를 리스트에 넣을 수 있을까?
인덱스를 통해서 숫자에 접근해보자!
풀이
def BT(idx):
# global idx
if len(dap) == M:
print(*dap)
return
else:
while idx != N:
num = nums[idx]
dap.append(num)
BT(idx+1)
idx+=1
dap.pop()
N,M = map(int, input().split())
nums = [1+i for i in range(N)]
idx = 0
dap = []
BT(idx)
N과M (1) 과 동일하게
메인 부분에서 입력을 받고
1~n 까지의 숫자를 미리 만들어주고 시작했다.
저번과는 다르게 인덱스를 통해서 nums의 값에 접근할 것이기 때문에
idx 라는 변수를 만들어 주었다.
BT 함수를 작성했다. 이번에는 idx를 인자로 받아온다.
global 선언을 통해서 idx 값을 증가시키는 방법도 생각 해 보았지만
위치에 맞게 idx 값을 증가시키는 것 보다는 이 방법이 편할 것 같아서 함수가 호출될 때 마다 idx 값을 증가시켜줬다.
가장 처음에 들어간 값에 대한 모든 함수 호출이 끝난 후에 idx 값을 증가시켜 주어서
리스트에 들어갔던 기준값이 다시 들어가지 않게 해 주었고
idx 값이 N이 되면 while문을 종료하게 만들어 주었다.
EX)
n,m 을 4, 2 라고 가정한다.
idx 가 0 일때 num 은 1이 된다.
따라서 1을 리스트에 넣은 이후에 함수를 호출한다. (기준값이 1인 대기상태)
함수를 호출할 때 idx를 1 증가시키기 때문에
idx 는 1이 되고 이때의 num 은 2가 된다.
리스트에 2를 추가로 넣으면 리스트의 길이는 m과 동일해 지고
리턴 해주기 때문에 BT(idx+1) 으로 돌아온다.
이때 직접 idx 를 1 증가시켜 주기 때문에 idx는 2가 되고 num 은 3이 된다. 이를 반복하다
idx가 4가 되면 while 문이 끝나기 때문에
(기준값이 1인 대기상태) 의 BT(idx+1) 위치로 돌아오고
다시 직접 idx 값을 증가시켜준다 이렇게 되면 idx는 1이 되고 리스트에는 아무것도 들어있지 않게 된다.
아직 idx 값이 4가 아니기 때문에 또 다시 while 문에 진입하고 위와 같은 순서를 반복한다.
느낀점
N과M (1) 을 풀어서인지 조금 더 편하게 푼 것 같다. 아직 n과m 시리즈가 많이 남아있는데
가능하면 모두 풀어서 백트래킹에 대해서 좀 더 확실하게 알고 문제에 접근하고 싶다.
하지만 백트래킹을 활용하면 된다는것을 스스로 알아차리기 위해서는 많은 연습이 필요할 것 같다.
개인적으로 아직 구현능력이 정~~~~~~~말 많이 떨어진다고 생각해서 시간이 날때 구현관련 문제를 많이 풀어보자
'컴퓨터 > Algorithm' 카테고리의 다른 글
백준 1759 암호 만들기 (파이썬) (0) | 2022.09.09 |
---|---|
백준 15649 N과 M (4) (파이썬) (0) | 2022.09.07 |
백준 15649 N과 M (1) (파이썬) (0) | 2022.09.05 |
백준 2667 단지번호붙이기(파이썬) (0) | 2022.09.04 |
백준 7576 토마토(파이썬) (0) | 2022.09.02 |