[백준, 15651번] N과 M(3) (백트래킹, DFS, Java)

문제설명

입력 & 출력

나의 풀이

문제 접근 방법

"백준 - N과 M (3)"문제는 백트래킹 시리즈로, 다음과 같은 요구사항이 존재합니다.

 

[Algorithm] 백트래킹(Backtracking) 알고리즘 알아보기

• 중복을 허용하지 않는다
  • 각 자리의 숫자는 중복되지 않도록 해야 합니다.
• 1부터 N까지의 수를 고른다
  • 선택할 수 있는 숫자는 1부터 N까지입니다.
• 오름차순으로 나열
  • 각 수열은 오름차순으로 배치해야 합니다.

---

여기서 중요한 포인트를 짚어보면,

 

• 같은 수를 여러 번 골라도 된다
  • 예: [1,1,1], [1,1,2], [1,2,1] 모두 가능
• "중복되는 수열을 여러 번 출력하면 안된다"
  • 이는 같은 구성의 수열이 여러 번 출력되면 안 된다는 의미
  • 예: [1,1,2]가 두 번 출력되면 안됨

 

전체 코드

 

빠른 입력처리를 위해서 BufferedReader클래스를 사용하여 입력을 받아주고, StringTokenizer클래스를 사용하여 입력을 공백으로 분리해줍니다.

 

이번 문제는 기존의 N과 M시리즈와 다르게, 1부터 N까지의 수를 고르는 것이기 때문에 start변수가 필요하지 않습니다.

 

• end: 수열에서 사용할 수 있는 최대 숫자 (N)
• idx: 현재 수열에서 채우고 있는 위치 (0부터 시작)

 

getSequence함수는 현재 위치(idx)를 기준으로, 매번 1부터 N까지의 모든 숫자를 시도합니다.

 

수열의 길이가 M이 될 때까지 각 위치에서 가능한 모든 숫자를 넣어보며, 길이가 M이 되면 그 수열을 결과에 추가합니다.

 

같은 숫자를 여러 번 사용할 수 있기 때문에 매번 1부터 시작하며, 이러한 방식으로 모든 가능한 수열을 사전 순으로 만들어냅니다.

 

 

N과 M 시리즈 문제

 

[백준, 15649번] N과 M(1) (백트래킹, Java)

[백준, 15650] N과 M (2) (백트래킹, Java)

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