C++의 아름다운 배열

<시간/>

1에서 N까지의 N개의 정수가 있다고 가정합니다. 다음 중 하나가 이 배열의 i번째 위치(1 <=i <=N)에 대해 참인 경우 이 N개의 숫자로 완전히 구성된 배열로 아름다운 배열을 정의합니다. -

i번째 위치의 숫자는 i로 나눌 수 있습니다.
i는 i번째 위치의 숫자로 나눌 수 있습니다.

따라서 입력이 2이면 결과도 2가 됩니다. 첫 번째 아름다운 배열은 [1,2]이기 때문입니다. 여기서 첫 번째 위치(i=1)의 숫자는 1이고 1은 i(i=1)로 나눌 수 있습니다. 그런 다음 두 번째 위치(i=2)의 숫자는 2이고 2는 i(i=2)로 나눌 수 있습니다. 두 번째 아름다운 배열은 [2, 1]입니다. 여기에서 첫 번째 위치(i=1)의 숫자는 2이고 2는 i(i=1)로 나눌 수 있습니다. 그런 다음 두 번째 위치(i=2)의 숫자는 1이고 i(i=2)는 1의 배수입니다.

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

방문 배열, end 및 pos를 취하는 재귀 메서드 solve()를 정의합니다. 위치는 처음에 1입니다.
pos =end + 1이면 ans를 1만큼 증가시키고 반환
범위 1에서 종료까지의 경우
- 내가 방문하지 않았고 pos가 0으로 나누어 떨어지거나 i가 0으로 나누어 떨어지면
  - 방문한 것으로 표시
  - 해결(방문, 종료, 위치 + 1)
  - 방문하지 않은 것으로 표시
메인 메소드에서 다음을 수행하십시오 -
ans :=0, 방문이라는 배열을 만듭니다.
call 해결(방문, N, 1)r
반환

이해를 돕기 위해 다음 구현을 살펴보겠습니다. −

예시

#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
   int ans;
   void solve(vector <bool>& visited, int end, int pos = 1){
      if(pos == end + 1){
         ans++;
         return;
      }
      for(int i = 1; i <= end; i++){
         if(!visited[i] && (pos % i == 0 || i % pos == 0)){
            visited[i] = true;
            solve(visited, end, pos + 1);
            visited[i] = false;
         }
      }
   }
   int countArrangement(int N) {
      ans = 0;
      vector <bool> visited(N);
      solve(visited, N);
      return ans;
   }
};
main(){
   Solution ob;
   cout << (ob.countArrangement(2));
}

C++의 아름다운 배열

예시

입력

출력