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)
- 방문하지 않은 것으로 표시
- 내가 방문하지 않았고 pos가 0으로 나누어 떨어지거나 i가 0으로 나누어 떨어지면
- 메인 메소드에서 다음을 수행하십시오 -
- 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)); }
입력
2
출력
2