1부터 N까지의 정수 N개가 있다고 가정해 보겠습니다. 이 N개의 숫자를 모두 사용해 만든 배열에서 임의의 위치 i(1 ≤ i ≤ N)에 대해 다음 조건 중 하나라도 성립하면, 그 배열을 아름다운 배열(Beautiful Arrangement)이라고 정의합니다.
- i번째 위치에 있는 숫자가 i로 나누어 떨어지는 경우
- i가 i번째 위치에 있는 숫자로 나누어 떨어지는 경우
예제 이해하기
예를 들어 입력이 2라면 정답은 2가 됩니다.
- [1, 2]: 1번 위치(i=1)의 숫자는 1이며, 1은 i=1로 나누어 떨어집니다. 2번 위치(i=2)의 숫자는 2이며, 2는 i=2로 나누어 떨어집니다.
- [2, 1]: 1번 위치(i=1)의 숫자는 2이며, 2는 i=1로 나누어 떨어집니다. 2번 위치(i=2)의 숫자는 1이며, i=2는 숫자 1로 나누어 떨어집니다.
즉, 조건을 만족하는 배열의 개수를 세는 것이 이 문제의 핵심입니다.
풀이 접근 방식
이 문제는 백트래킹(backtracking)을 활용하면 깔끔하게 해결할 수 있습니다. 각 위치마다 조건을 만족하는 숫자를 하나씩 채워 나가고, 더 이상 진행할 수 없으면 이전 상태로 되돌아가 다른 후보를 시도하는 방식입니다. 구체적인 단계는 다음과 같습니다.
- 방문 여부를 저장하는
visited배열, 마지막 위치end, 현재 채울 위치pos를 매개변수로 받는 재귀 함수solve()를 정의합니다.pos의 초기값은 1입니다. pos가end + 1과 같아지면 모든 위치를 성공적으로 채운 것이므로 정답 변수ans를 1 증가시키고 함수를 종료합니다.- i를 1부터
end까지 반복하면서, i를 아직 사용하지 않았고(i 미방문)pos % i == 0또는i % pos == 0을 만족한다면 다음을 수행합니다.- i를 방문 처리합니다.
solve(visited, end, pos + 1)을 재귀 호출하여 다음 위치를 채웁니다.- 재귀 호출이 끝나면 i를 다시 미방문 상태로 되돌려(백트래킹) 다른 조합을 탐색할 수 있게 합니다.
- 메인 함수에서는
ans를 0으로 초기화하고visited배열을 생성한 뒤,solve(visited, N, 1)을 호출하고 그 결과로ans를 반환합니다.
C++ 구현 예제
위 알고리즘을 C++ 코드로 구현하면 다음과 같습니다.
#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
복잡도 분석
각 위치마다 최대 N개의 숫자를 시도하므로 시간 복잡도는 최악의 경우 O(N!)이지만, 나누어 떨어지는 조건 덕분에 실제 탐색 공간은 크게 줄어듭니다. 공간 복잡도는 방문 배열과 재귀 호출 스택에 의해 O(N)입니다.