#include <bits/stdc++.h>
using namespace std;
int main(void)
{
int n, k;
int in[10];
cin >> n >> k;
for (int i = 0; i < n; i++)
{
cin >> in[i];
}
int cnt = 0;
for (int i = n - 1; i >= 0; i--)
{
while (k / in[i])
{
cnt += k / in[i];
k = k % in[i];
}
}
printf("%d", cnt);
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;
}
연결요소 문제와 유사하게 방문하지 않은 정점을 찾아서 dfs / bfs 순회를 해주면 된다.
여기서 정점의 정보는 [행,열]이 된다. 즉, (x,y)값을 한개의 정점으로 생각하면 됨.
그리고 이런 문제에서는 인접 정점을 찾는 방법은 아래와 같이 한개 정점 (x,y)에서 위/아래/좌/우로 이동을 위해 변경되야할 좌표값을 아래 배열과 같이 넣어두고 for문을 돌리면 간단하게 구현 할 수 있다.
int dx[] = { 0,0,1,-1 }; int dy[] = { 1,-1,0,0 };
연속된 숫자중 1개 자리씩만 입력을 받고 싶을경우 아래 코드를 이용하면 된다.
scanf("%1d", &input[i][j]);
아래 소스코드는 bfs를 사용해서 해결하였다.
#include <bits/stdc++.h>
using namespace std;
int input[30][30];
int dx[] = { 0,0,1,-1 };
int dy[] = { 1,-1,0,0 };
int n;
int res[25 * 25];
#define Dangi_Start_Num 2 //플러드 필에 사용되는 단지 시작 번호
void bfs(int x, int y, int cnt) {
queue<pair<int, int>> q;
q.push(make_pair(x, y));
input[x][y] = cnt;
while (!q.empty()) {
x = q.front().first;
y = q.front().second;
q.pop();
for (int k = 0; k < 4; k++) {
int nx = x + dx[k];
int ny = y + dy[k];
if (0 <= nx && nx < n && 0 <= ny && ny < n) { //input 배열의 범위밖을 참조하지 않도록 하기 위해
if (input[nx][ny] == 1) {
q.push(make_pair(nx, ny));
input[nx][ny] = cnt;
}
}
}
}
}
int main() {
//지도 정보 입력 받기
scanf("%d", &n);
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
scanf("%1d", &input[i][j]);
}
}
//플러드 필
int cnt = Dangi_Start_Num;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (input[i][j] == 1) {
bfs(i, j, cnt++);
}
}
}
//단지 개수 출력
printf("%d\n", cnt - Dangi_Start_Num);
//플러드 필된 값(즉, 단지번호) 별로 몇개가 있는지 개수를 셈
//그 개수를 res배열에 index는 단지배열이고, 그곳에 그 단지의 개수를 저장해둠.
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (input[i][j] != 0)
res[input[i][j] - Dangi_Start_Num] += 1;
}
}
//res를 오른 차순으로 정렬함.
sort(res, res + cnt - Dangi_Start_Num);
//단지별 개수를 오름차순으로 출력함.
for (int i = 0; i < cnt - Dangi_Start_Num; i++) {
printf("%d\n", res[i]);
}
return 0;
}
연결 요소의 개수의 경우, DFS나 BFS를 공부를 공부한 후라면 간단하게 해결 가능하다.
모든 정점을 대상으로 방문한 적이 없는 정점이 있으면 그 정점을 기준으로 DFS 또는 BFS순회를 통해 방문했다는 체크를 해둔다. 그 후에도 아직 방문하지 않은 정점이 있다면 또 DFS나 BFS를 통해 순회하면서 방문했다는 체크를 하면 된다.
#include <bits/stdc++.h>
using namespace std;
int n, l;
vector <int> a[1005];
int visited[1005] = { 0, };
void dfs_l(int s) {
int i;
visited[s]++;
for (i = 0; i < a[s].size(); i++){
if (visited[a[s][i]] == 0){
dfs_l(a[s][i]);
}
}
}
int main()
{
int i, n1, n2, cnt = 0;
scanf("%d %d", &n, &l);
//간선 정보를 입력 받아 그래프 만들기
for (i = 0; i < l; i++){
scanf("%d %d", &n1, &n2);
a[n1].push_back(n2);
a[n2].push_back(n1);
}
//DFS 순회시에 인접 정점중에 정점번호가 작은 값부터 순회하기 위해 정렬
//이번 문제에서는 굳이 없어도 됨.
for (int i = 0; i < n; i++) {
sort(a[i].begin(), a[i].end());
}
//방문하지 않은 정점을 발견하면 DFS순회함.
//DFS가 호출되는 횟수가 연결요소의 개수가 됨.
for (int i = 1; i <= n; i++){
if (visited[i] == 0){
dfs_l(i);
cnt++;
}
}
printf("%d", cnt);
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);
}
}
자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.
1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열
N=4, M=4가 주어지면, 아래와 같이 12(4*3)개의 경우가 발생한다.
아래 1 4 와 4 1과 같이 순서가 다른 경우는 다른 것으로 판단해야 함.
1 2 1 3 1 4 2 1 2 3 2 4 3 1 3 2 3 4 4 1 4 2 4 3
"중복 없이"라는 조건이 있음으로 한번 수열에 포함된 수는 수열을 완성할때까지 다시 포함되면 안됨으로 포함 여부를 판단하기 위해 included라는 배열을 사용한다.
n = 4, m = 2를 입력하면, 아래와 같은 순서로 실행된다.
"1. go(4,2)" : nm에 1추가 (nm = 1)
"2. go(4,2)" : nm에 2추가 (nm = 1,2)
"3. go(4,2)" : nm.size()가 m임으로 nm의 내용 1,2 출력 후 return
"2. go(4,2)" 로 돌아감. nm에서 2를 pop_bakc하고, for문을 통해 i 증가시킨 후 nm에 3을 추가함.
#include <bits/stdc++.h>
using namespace std;
bool included[10]; //중복 체크
vector <int> nm;
void NM1(int, int);
int main() {
int n, m;
cin >> n >> m;
NM1(n, m);
return 0;
}
void NM1(int n, int m) {
if (nm.size() == m) {
for (int i = 0; i < m; i++) {
cout << nm[i] << " ";
}
cout << '\n';
return;
}
for (int i = 1; i <= n; i++) {
if (!included[i]) {
included[i] = true;
nm.push_back(i);
NM1(n, m);
nm.pop_back();
included[i] = false;
}
}
}
