[백준, 15652번] N 과 M (4) (백트래킹, Java)

문제설명

입력 & 출력

나의 풀이

문제 접근 방법

"백준 - N과 M (4)"문제는 백트래킹 시리즈입니다. 이전 문제와 같은 맥락으로 백트래킹으로 효율적으로 풀 수 있습니다.

 

이번 (4)문제에서는 다음과 같은 조건이 있습니다.

• 1부터 N까지 자연수 중에서 M개를 고른 수열
• 같은 수를 여러 번 골라도 된다.
• 고른 수열은 비내림차순이어야 한다.
  • 길이가 K인 수열 A가 A1 ≤ A2 ≤ ... ≤ AK-1 ≤ AK를 만족하면, 비내림차순이라고 한다.

[TIL, 일일 회고] 2024.12.11 - 정렬 방식의 이해: 오름차순, 내림차순, 비내림차순, 비증가순

즉, 비내림차순은 크거나 같은 값을 가지는 수열을 구하면 되는 문제입니다.

 

전체 코드

 

"백준 - N과 M (2)"문제와 비슷하지만 해당 문제와 다른 점은 수열의 조건입니다.

 

(2)번 문제에서는 "고른 수열은 오름차순이어야 한다." 라는 조건이 존재했지만, (4)번 문제에서는 중복을 허용하고, 비내림차순이라는 조건이 존재합니다.

 

즉, 수열을 만들 때 크거나 같은 값이 수열에 들어가야하기 떄문에 수열 배열(sequence)의 삽입 부분만 주의한다면 어렵지 않게 풀 수 있습니다.

 

재귀 호출을 통해 수열을 생성할 때, 수열의 최댓값(end)은 고정되어 있으며, 시작 값(start)은 중복을 허용하도록 i 값을 그대로 전달합니다.

 

이 과정에서 i를 그대로 전달하므로, 재귀 호출에서도 동일한 i가 포함될 수 있습니다. 따라서 현재 선택한 수와 같거나 더 큰 수를 선택할 수 있는 구조가 형성됩니다.