[BOJ 27260 // C++] Красивые перестановки

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

 

이번에 볼 문제는 백준 27260번 문제인 Красивые перестановки이다.
문제는 아래 링크를 확인하자.

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

27260번: Красивые перестановки

1부터 N까지로 구성된 모든 순열에 대하여 인접한 두 원소의 곱의 합이 k의 배수인지를 확인하는 문제이다.

 

가능한 모든 순열을 생성하는 코드를 작성해 문제를 해결하자.

 

아래는 제출한 소스코드이다.

#include <iostream>
#include <vector>
using namespace std;

int N, K;
bool visited[11];
vector<int> vec;
int val, ans;

void func(int cnt) {
	if (cnt == N) {
		if (val % K == 0) ans++;
	}
	else {
		for (int i = 1; i <= N; i++) {
			if (visited[i]) continue;
			val += vec.back() * i;
			visited[i] = 1;
			vec.emplace_back(i);
			func(cnt + 1);
			vec.pop_back();
			visited[i] = 0;
			val -= vec.back() * i;
		}
	}
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> N >> K;

	for (int n = 1; n <= N; n++) {
		visited[n] = 1;
		vec.emplace_back(n);
		func(1);
		vec.pop_back();
		visited[n] = 0;
	}

	cout << ans;
}