728x90
15666번: N과 M (12)
한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해
www.acmicpc.net
백트래킹 문제다.
이번 조건은
같은 수를 여러번 골라도 되고,
비내림차순 수열이어야 한다는 것이다.
여기서 같은 수라는 것은 같은 인덱스에 있는 수를 의미한다.
그러므로 visited 리스트를 사용할 필요가 없다.
그리고 backTracking함수의 인자로 현재 탐색한 인덱스를 넘겨줘서
다음 backTracking시 for문의 시작값으로 넣어줘서 비내림차순으로 만들어준다.
# 15666번: N과 M (12)
n, m = map(int, input().split())
arr = sorted(list(map(int, input().split())))
result = []
def backTracking(num):
if len(result) == m:
print(*result)
return
remember = 0
for i in range(num, n):
if arr[i] != remember:
result.append(arr[i])
remember = arr[i]
backTracking(i)
result.pop()
backTracking(0)
728x90
'알고리즘 > 백준' 카테고리의 다른 글
6603번: 로또 (0) | 2024.04.12 |
---|---|
1182번: 부분 수열의 합 (0) | 2024.04.09 |
15665번: N과 M(11) (0) | 2024.04.09 |
15664번: N과 M(10) (0) | 2024.04.09 |
15663번: N과 M(9) (0) | 2024.04.04 |
728x90
15666번: N과 M (12)
한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해
www.acmicpc.net
백트래킹 문제다.
이번 조건은
같은 수를 여러번 골라도 되고,
비내림차순 수열이어야 한다는 것이다.
여기서 같은 수라는 것은 같은 인덱스에 있는 수를 의미한다.
그러므로 visited 리스트를 사용할 필요가 없다.
그리고 backTracking함수의 인자로 현재 탐색한 인덱스를 넘겨줘서
다음 backTracking시 for문의 시작값으로 넣어줘서 비내림차순으로 만들어준다.
# 15666번: N과 M (12)
n, m = map(int, input().split())
arr = sorted(list(map(int, input().split())))
result = []
def backTracking(num):
if len(result) == m:
print(*result)
return
remember = 0
for i in range(num, n):
if arr[i] != remember:
result.append(arr[i])
remember = arr[i]
backTracking(i)
result.pop()
backTracking(0)
728x90
'알고리즘 > 백준' 카테고리의 다른 글
6603번: 로또 (0) | 2024.04.12 |
---|---|
1182번: 부분 수열의 합 (0) | 2024.04.09 |
15665번: N과 M(11) (0) | 2024.04.09 |
15664번: N과 M(10) (0) | 2024.04.09 |
15663번: N과 M(9) (0) | 2024.04.04 |