[c++] 백준 15651 N과 M(3) (백트래킹인데 조금 수정)

0. [c++] 백준  - 15651

https://www.acmicpc.net/problem/15651

1. 풀이

이 문제는 백트래킹 기법을 적용해서 푸는 문제였는데, 간단히 if문을 활용하면 n^2의 시간 내에 풀이가 가능하였다.

방법을 설명하자면, 

1. 배열을 선언하고 가장 마지막 배열에 1을 지속적으로 더해준다.

2. 배열의 크기를 지속적으로 검사하는데, 만일 각 항목의 크기가 입력으로 들어온 최대 범위를 넘으면 1로 바꾸고 올림을 취해준다.(arr[N]이 최대값을 넘었으면 arr[N-1]++ 을 해준다.)

이러한 방법으로 주어진 값에 대해 원하는 출력을 할 수 있었다.

2. 소스코드

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42

#include<iostream>   using namespace std;   int arr[8];   int main() {     ios_base::sync_with_stdio(0);     cin.tie(0);     int N, M;       cin >> N >> M;       //우선 배열을 초기화     for (int i = 1;i <= M;i++) {         arr[i] = 1;     }     bool flag = false;     while(1) {         flag = true;         for (int i = 1;i <= M;i++) {             if (!flag)                 break;             if (arr[i] != N)                 flag = false;         }         for (int i = 1;i <= M;i++)             cout << arr[i] << " ";         cout << "\n";         if (flag)             break;         arr[M]++;         for (int i = M; i >= 1;i--) {             if (arr[i] > N) {                 arr[i] = 1;                 arr[i - 1]++;             }         }                  }     cout << endl; }

cs

3. 참고

질문이나 지적 있으시면 댓글로 남겨주세요~

도움 되셨으면 하트 꾹!