[BOJ/백준] 15651번: N과 M(3) (c++)

N과 M(3) 문제링크

해당 문제는 백트래킹 연습문제로 유명한 N과 M시리즈이다. 처음엔 이해가 어려웠는데 이 시리즈를 풀다보니 이해하기 쉬웠던 것 같다.

✨문제

• 해당 문제는 중복을 만족하는 수열을 출력해야한다.

✔️Solution

조건

• 같은 수 중복을 허용한다.
• 현재 내림차순, 오름차순 상관없다.

백트래킹으로 가능한 조건일 경우를 확인하고, 부모 노드로 돌아갈 수 있도록 설정한다.

풀이

• 현재 M자리수의 수열이므로 M자리수를 채워진 조건이면 수열을 출력한다.
• 중복이 가능하므로 다음에 시작할 반복문의 시작숫자는 현재 index의 숫자이다. (ex. 2자리 수열인 경우, 4에서 다음으로 넘어갈 때 4도 가능하므로 다음 반복문은 4부터 시작하는 것이다.)

이때 반복문을 살펴보면

for(int i=1; i<=n; i++){
        nums[index] = i;
        backTracking(index+1);
}

• num이라는 배열에 현재 index에 차례대로 저장한다.
• 저장 후 다음으로 넘어가는데 index+1을 하여 현재 중복을 허용할 수 있도록 한다.

// 가지치기
    if(index == m){
        for(int i=0; i<nums.size(); i++){
            cout<< nums[i] << " ";
        }
        cout << '\n';
        return;
  }
    

• 이때 index가 현재 수열의 자릿수를 만족하는 경우 조건을 만족했기 때문에 num에 저장한 수열을 출력한다.

  전체 코드

  void backTracking(int index){
  
     // 가지치기
     if(index == m){
         for(int i=0; i<nums.size(); i++){
             cout<< nums[i] << " ";
         }
         cout << '\n';
         return;
     }
  
     for(int i=1; i<=n; i++){
         nums[index] = i;
         backTracking(index+1);
     }

}

백트래킹 코드이다 !