#include "bits/stdc++.h" using namespace std; //부분수열의 합 int arr[20], n, m, cnt;
void recursive(int start, int level, int sum) { if (start == level && sum == m) { cnt++; } for (int i=start; i<n; i++) { recursive(i+1, level, sum+arr[i]); } }
int main() { cin >> n >> m; for (int i=0; i<n; i++) { cin >> arr[i]; } for (int i=1; i<=n; i++) { recursive(0, i, 0); } printf("%d", cnt); }
#include <bits/stdc++.h>
using namespace std;
//최소공배수
int gcd(int a, int b) {
while (b != 0) {
int last = a % b;
a = b;
b = last;
}
return a;
}
int main() {
int t, a, b;
cin >> t;
while (t--) {
cin >> a >> b;
int g = gcd(a, b);
printf("%d\n", (a*b)/g);
}
}
#include<bits/stdc++.h>
using namespace std;
/*함수3 - 형성평가4
첫 번째는 1, 두 번째는 2, 세 번째부터는 앞의 두 수의 곱을 100으로 나눈 나머지로 이루어진 수열이 있다.
100 이하의 자연수 N을 입력받아 재귀함수를 이용하여 N번째 값을 출력하는 프로그램을 작성하시오.
입력 예
8
출력 예
92
*/
int d[1004];
int f(int n)
{
int result;
if(n==1) return 1;
if(n==2) return 2;
if(d[n]>0){
return d[n];
}
else{
d[n] = (f(n-1)*f(n-2))%100;
return d[n];
}
}
int main()
{
int n,k;
scanf("%d",&n);
k=f(n);
printf("%d",k);
return 0;
}
#include <bits/stdc++.h>
using namespace std;
/*
함수3 - 형성평가1
자연수 N을 입력받아 1부터 N까지 출력을 하되 n-1번째 값은 n번째 값을 2로 나눈 몫이 되도록 하는 프로그램을 작성하시오.
*/
void f(int n){
if(n == 0) return;
f(n/2);
printf("%d ", n);
}
int main()
{
int n;
scanf("%d", &n);
f(n);
return 0;
}
N-Queen문제 생각보다 어렵죠? 아마도 N-Queen문제에서 막혀서 찾아오셨다면, 아마도 백트랙킹 / 재귀함수에 대해서 아주 조금 이해가 힘드셔서 오셨을것 같네요.^^ 아래 코드보시면서 도움 되시기 바랍니다.
각 행을 한개씩 내려가면서 Queen을 놓을 곳을 찾아가면 될것 같다.
첫번째 행의 어느 열에 Queen을 위치시키면, 그 열과 대각선 방향을 더이상 Queen을 놓을수 없음을 표시해야 한다.
bool check_right_up[100]; //이미 대각선 오른쪽 위로 queen이 있는지 확인 위 코드는 아래 그림을 보고 이해할 수 있길 바랍니다. 대각선의 각 cell의 행값 + 열값은 unique하다는 걸 이용해서,
그 unique한 값을 배열의 index로 사용해서, 그 대각선에 이미 Queen이 위치해 있음을 판단하면 됩니다.
bool check_right_down[100]; //이미 대각선 오른쪽 아래로 queen이 있는지 확인
아래 그림은 행-열을 한 값을 표시하고 있다. 음수가 발생하니, 모든 값들에 N을 더하면,
1,2,3,4,5,6,7 로 unique한 값을 만들수 있고, 이것을 배열의 index로 이용하면 됩니다.
#include <bits/stdc++.h>
using namespace std;
bool a[15][15];
int n;
bool check_col[15]; //이미 그 열에 queen이 있는지 확인
bool check_right_up[100]; //이미 대각선 오른쪽 위로 queen이 있는지 확인
bool check_right_down[100]; //이미 대각선 오른쪽 아래로 queen이 있는지 확인
void check_onoff(int row, int col, bool onoff)
{
check_right_up[row + col] = onoff;
check_right_down[row - col + n] = onoff;
check_col[col] = onoff;
a[row][col] = onoff;
}
bool check(int row, int col) {
// 같은 열 확인
if (check_col[col]) {
return false;
}
// 오른쪽 위방향 대각선 확인 (왼쪽 아래도^^)
if (check_right_up[row + col]) {
return false;
}
// 오른쪽 아래 방향 대각선 확인 (왼쪽 위도^^)
if (check_right_down[row - col + n]) {
return false;
}
return true;
}
int N_Queen(int row) {
if (row == n) {
return 1;
}
int cnt = 0;
for (int col = 0; col < n; col++) {
if (check(row, col)) { //이 row, col위치에 놓을수 있을지 확인
check_onoff(row, col, true); //놓을 수 있으니까, 그 위치 관련해서 놓았다는 표시를 함
cnt += N_Queen(row + 1); //다음 행에 queen을 놓으로 감.
check_onoff(row, col, false); //row, col 기준으로 확인해보 후 임으로, 다시 해제함.
}
}
return cnt;
}
int main() {
cin >> n;
cout << N_Queen(0) << '\n';
return 0;
}
길이가 K인 수열 A가 A1≤ A2≤ ... ≤ AK-1≤ AK를 만족하면, 비내림차순이라고 한다.
따라서 N과 M (2)에서 재귀함수의 첫번째 인자만, i+1이 아니랑 i를 주면 된다.
즉, i값을 포함해서 다음 수를 정해나가는 형태이다. 왜냐? 중복을 허용하기 때문이다.
#include <bits/stdc++.h>
using namespace std;
vector <int> nm;
void NM4(int, int, int);
int main() {
int n, m;
cin >> n >> m;
NM4(1, n, m);
return 0;
}
void NM4(int s, int n, int m) {
if (nm.size() == m) {
for (int i = 0; i < m; i++) {
cout << nm[i] << " ";
}
cout << '\n';
return;
}
for (int i = s; i <= n; i++) {
nm.push_back(i);
NM4(i, n, m); //현재 nm vector에 넣은 수 이후 수를 확인 한다. (오름차순)
nm.pop_back();
}
}
내 생각에는 N과 M(1)보다 풀이에 접근하기 더 쉬운 문제라고 생각한다. 내기준으로는 "N과 M(0)" 이 맞을듯.^^
#include <bits/stdc++.h>
using namespace std;
vector <int> res;
void NM3(int n, int m) {
if (res.size() == m) {
for (int i = 0; i < m; i++) {
cout << res[i] << " ";
}
cout << '\n';
return;
}
for (int i = 1; i <= n; i++) {
res.push_back(i);
NM3(n, m);
res.pop_back();
}
}
int main() {
int n, m;
cin >> n >> m;
NM3(n, m);
return 0;
}
이를 위해서 현재 선택된 수 보다 1개 높은 위치의 수를 부터 수열을 만들어 나가야 한다.
이를 위해서 NM2(재귀함수)에 start해야 할 위치를 인자로 넘겨주는 부분이 수정되었다.
그리고 항상 다음 수를 대상으로 수열을 만들어 나가기 때문에 중복체크를 위한 included배열은 필요없다.
#include <bits/stdc++.h>
using namespace std;
//bool included[10]; //중복 체크
vector <int> nm;
void NM2(int, int, int);
int main() {
int n, m;
cin >> n >> m;
NM2(1, n, m);
return 0;
}
void NM2(int s, int n, int m) {
if (nm.size() == m) {
for (int i = 0; i < m; i++) {
cout << nm[i] << " ";
}
cout << '\n';
return;
}
for (int i = s; i <= n; i++) {
//if (!included[i]) {
//included[i] = true;
nm.push_back(i);
NM2(i + 1, n, m); //현재 nm vector에 넣은 수 이후 수를 확인 한다. (오름차순)
nm.pop_back();
//included[i] = false;
//}
}
}
두번째 풀이
각 수들을 포함 하거나 또는 포함 하지않으면서 다음수로 넘어가는 형태
#include <bits/stdc++.h>
using namespace std;
vector <int> nm;
void NM2(int level, int n, int m);
int main() {
int n, m;
cin >> n >> m;
NM2(1, n, m);
return 0;
}
void NM2(int level, int n, int m) {
if (nm.size() == m) {
for (int i = 0; i < m; i++) {
cout << nm[i] << " ";
}
cout << '\n';
return;
}
if (level > n) return;
nm.push_back(level);
NM2(level + 1, n, m);
nm.pop_back();
NM2(level + 1, n, m);
}
세번째 풀이
배열을 사용해서 결과값을 저장한 위치에 해당하는 index 인자를 관리해주고,
오름차순을 위해 다음 수를 지정해주는 start를 관리해 주는 형태
#include <bits/stdc++.h>
using namespace std;
int res[10];
void go(int index, int start, int n, int m);
int main() {
int n, m;
cin >> n >> m;
go(0, 1, n, m);
return 0;
}
void go(int index, int start, int n, int m) {
if (index == m) {
for (int i = 0; i < m; i++) {
cout << res[i];
if (i != m - 1) cout << ' ';
}
cout << '\n';
return;
}
for (int i = start; i <= n; i++) {
res[index] = i;
go(index + 1, i + 1, n, m);
}
}
