#include <iostream>
#include <vector>
using namespace std;
int n, s;
int cnt = 0;
void solve(vector<int>& input, int index, int sum) {
if(index == n){ // input의 끝까지 탐색하였을 경우
if (sum == s) cnt++; // 부분수열의 합이 s이면 count
return;
}
// 현재 숫자를 선택하는 경우
solve(input, index + 1, sum + input[index]);
// 현재 숫자를 선택하지 않는 경우
solve(input, index + 1, sum);
}
int main() {
cin >> n >> s;
vector<int> input(n);
for (int i = 0; i < n; i++) cin >> input[i];
solve(input, 0, 0);
if (s == 0) cnt--; // ** 아무것도 선택하지 않은 경우에도 포함이므로 삭제 **
cout << cnt << endl;
return 0;
}
부분수열의 합으로 나올 수 '없는' '가장 작은' 자연수
(1) 부분수열의 합이 될 수 있는 숫자들의 배열을 만든다. (2) 정렬한다. (3) 포함되어있지 않은 가장 작은 자연수를 찾아 반환한다.
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int n;
vector<int> sums;
void partialSum(vector<int>& S, int index, int sum) {
if (index == n) {
sums.push_back(sum); // 6 3 7 8 5 1 2
return;
}
partialSum(S, index + 1, sum + S[index]);
partialSum(S, index + 1, sum);
}
int main() {
cin >> n;
vector<int> S(n); // 5 1 2
for (int i = 0; i < n; i++) cin >> S[i];
partialSum(S, 0, 0);
sort(sums.begin(), sums.end()); // 오름차순으로 정렬
if (sums[1] != 1) {
cout << 1 << endl;
return 0;
}// (맨 앞은 0)
int index = 2, m = sums.size();
for (index = 2; index < m; index++)
if (sums[index - 1] + 1 < sums[index]){
cout << sums[index - 1] + 1;
return 0;
}
if (index == m) cout << sums[index - 1] + 1;
return 0;
}
또 다른 코드에서는 bool형의 배열을 만들어서, 만들 수 있는 값을 true로 표시하였다. 그리고 구현문에서 최초로 false 값을 가진 인덱스를 찾아 반환하였다.
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int n;
vector<int> results;
void calc(vector<int>& A, int ret, int index, int plus, int minus, int multi, int divide) {
if (index == n) {
results.push_back(ret);
return;
}
if (plus > 0) calc(A, ret + A[index], index + 1, plus - 1, minus, multi, divide);
if (minus > 0) calc(A, ret - A[index], index + 1, plus, minus - 1, multi, divide);
if (multi > 0) calc(A, ret * A[index], index + 1, plus, minus, multi - 1, divide);
if (divide > 0) calc(A, ret / A[index], index + 1, plus, minus, multi, divide - 1);
}
int main() {
cin >> n;
vector<int> A(n), sign(4);
for (int i = 0; i < n; i++) cin >> A[i];
for (int i = 0; i < 4; i++) cin >> sign[i];
calc(A, A[0], 1, sign[0], sign[1], sign[2], sign[3]);
sort(results.begin(), results.end());
cout << results[(int)results.size() - 1] << endl << results[0] << endl;
return 0;
}
테트로미노의 갯수를 최대로 한다. 핵심은 완전 탐색 재귀이고, 아래와 같은 로직을 사용하여 해결하였다. (1) 테트로미노 배치를 어떻게 표현할지 (2) 배치하는 모든 경우를 탐색하며 칸에 쓰인 수들의 합을 구한다. (3) 합의 최댓값을 구해서 출력한다.
#include <iostream>
#include <vector>
using namespace std;
int n, m; // 세로 가로
int board[501][501];
// board에서 정사각형을 오른쪽 아래로 채워나간다.
int block[9][3][2] = {
// shape1
{{0, 1}, {0, 2}, {0, 3}},
{{1, 0}, {2, 0}, {3, 0}},
// shape2
{{0, 1}, {1, 0}, {1, 1} },
// shape3
{{1, 0}, {2, 0}, {2, 1}},
{{0, 1}, {0, 2}, {1, 2}},
// shape4
{ {1, 0}, { 1, 1 }, { 2, 1 }},
{{0, 1}, {1, 1}, {1, 2}},
// shape5
{{0, 1}, {0, 2}, {1, 1}},
{{1, 0}, {1, 1}, {2, 0}}
};
int maxValue = 0;
void calc(int visited[501][501], int y, int x, int sum) {
if (y == n && x == m) {
if (maxValue < sum) maxValue = sum;
return;
}
visited[y][x] = true;
for (int shape = 0; shape < 9; shape++) { // 가능한 모든 경우를 놓는다.
for (int part = 0; part < 3; part++) {
int nextY = y + block[shape][part][0];
int nextX = x + block[shape][part][1];
if (!visited[nextY][nextX])
calc(visited, nextY, nextX, sum + board[nextY][nextX]);
}
}
}
int main() {
cin >> n >> m;
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++)
cin >> board[i][j];
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++) {
int visited[501][501] = { 0, };
calc(visited, i, j, 0);
}
}
NxM 행렬을 채우는 완전탐색의 경우에는 위와 같이 dy, dx 배열을 만들어서 현재 시점으로 모든 칸을 이동하는 경우를 탐색할 수 있다. ⇒ 이런 경우에는 아래와 같은 예외처리가 필수다.
if (y < 0 || y >= n || x < 0 || x >= m) return;
if (visited[y][x]) return;
브루트포스는 재귀를 수행하고 다시 visited[y][x] = false와 같이 상태 저장을 취소하는 코드가 들어있음을 확인
정답코드