DP문제 풀이의 감을 잡으면 DP만큼 쉬운 문제가 없다고들 하는데, 나는 감이 아직도 안온다;;
앞으로 단순 점화식만 소개하는 것이 아니라, 어떻게 그 점화식을 떠올리게 되었는지도 적을 예정이니 재미삼아 읽어보는 것도 좋을 것 같다.
DP를 구현하는 방법은 크게 두 가지가 있다. 재귀를 이용한 Top-Down 방식과 for문을 이용한 Bottom-Up방식이 있다.자세한 내용은 동적 계획법1의 첫번째 문제인 피보나치 문제에서 설명해보겠다.
아 ! 한가지 Tip을 드리자면, 가끔 문제를 풀 때 \(1,000,000,009\)같이 매우 큰 소수로 나눈 나머지를 답으로 내라는 문제들이 있다.이럴 땐, 꼭!!!! DP나 Memorization쪽을 고려해보자. 왜냐하면, 저렇게 큰 소수로 나눈 나머지가 답으로 나오는 문제들은 적어도 저 소수보다 많은 경우가 나온다는 말인데... 그 경우를 하나하나 세면 무조건 시간초과일 것이다.
연산자 개수가 10개 밖에 안돼서 next_permutation으로 해결하는 방법도 있다.
1. 백트래킹
#include <bits/stdc++.h>
using namespace std;
int n;
int num[12];
int cal[4];
int maxANS = -1'000'000'001; // 답의 범위는 -10억 ~ 10억
int minANS = 1'000'000'001;
void recur(int sum, int cur) {
// 한번의 탐색이 끝나면, 최댓값 최솟값 갱신
if (cur == n) {
maxANS = max(maxANS, sum);
minANS = min(minANS, sum);
return;
}
for (int i = 0; i < 4; ++i) {
// i번 연산자가 남아있지 않은 경우 다음 연산자로 넘어감
if (cal[i] == 0) continue;
// i번 연산자를 1개 사용
--cal[i];
if (i == 0) recur(sum + num[cur], cur + 1);
else if (i == 1) recur(sum - num[cur], cur + 1);
else if (i == 2) recur(sum * num[cur], cur + 1);
else if (i == 3) recur(sum / num[cur], cur + 1);
// 사용이 끝났으니 사용한 연산자 반납
++cal[i];
}
}
int main() {
ios::ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
cin >> n;
for (int i = 0; i < n; ++i) cin >> num[i];
for (int i = 0; i < 4; ++i) cin >> cal[i];
recur(num[0], 1);
cout << maxANS << '\n' << minANS;
return 0;
}
2. next_permutation()
#include <bits/stdc++.h>
using namespace std;
int num[11];
int maxANS = -1'000'000'001;
int minANS = 1'000'000'001;
vector<int> calc;
int main()
{
ios::ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int n, numOfCases;
cin >> n;
for (int i = 0; i < n; i++)
cin >> num[i];
// 연산자 나열
for (int i = 0; i < 4; i++)
{
cin >> numOfCases;
while (numOfCases--) calc.push_back(i);
}
// 나올 수 있는 경우의 수 계산 == 팩토리얼 연산
numOfCases = 1;
for (int i = 1; i <= n - 1; i++) numOfCases *= i;
while(numOfCases--) {
int tmp = num[0];
for (int j = 1; j < n; j++)
{
switch (calc[j - 1])
{
case 0:
tmp += num[j];
break;
case 1:
tmp -= num[j];
break;
case 2:
tmp *= num[j];
break;
case 3:
tmp /= num[j];
break;
}
}
minANS = min(minANS, tmp);
maxANS = max(maxANS, tmp);
next_permutation(calc.begin(), calc.end()); // 다음 경우
}
cout << maxANS << '\n' << minANS;
return 0;
}
\(((x / 3), (y / 3))\)번 정사각형 안에 어떤 수 n이 존재하는지 (하단 그림 참조)
확인해주면 된다.
1. bool 배열로 구현
#include <bits/stdc++.h>
using namespace std;
int sudoku[9][9];
bool row[9][10]; // 행
bool col[9][10]; // 열
bool block[3][3][10]; // 3x3 정사각형
vector<pair<int, int>> blank; // 빈칸들의 좌표
void recur(int cur) {
// 모든 칸이 채워졌다면 출력 후, exit(0)을 통해 바로 프로그램 종료
if (blank.size() == cur) {
for (int i = 0; i < 9; ++i) {
for (int j = 0; j < 9; ++j) cout << sudoku[i][j] << ' ';
cout << '\n';
}
exit(0);
}
int x = blank[cur].first;
int y = blank[cur].second;
for (int i = 1; i < 10; ++i) {
// i라는 숫자가 현재 칸이 속한 행, 열, 3x3 정사각형 안에 존재하는 지 확인
// 한 곳이라도 존재하면 다음 숫자로 넘어감
if (row[x][i] || col[y][i] || block[x / 3][y / 3][i]) continue;
// (x, y)에 i라는 숫자를 채워넣음
row[x][i] = true;
col[y][i] = true;
block[x / 3][y / 3][i] = true;
sudoku[x][y] = i;
recur(cur + 1); // 다음 칸으로 넘어가기
// 호출한 재귀함수가 리턴됐다는 것은, 현재 빈칸에 i라는 숫자가 들어가면 안된다는 의미
// 다른 숫자를 채워넣기 위해, (x, y)에서 i라는 숫자를 제거
row[x][i] = false;
col[y][i] = false;
block[x / 3][y / 3][i] = false;
sudoku[x][y] = 0;
}
}
int main() {
ios::ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
for (int i = 0; i < 9; ++i) for (int j = 0; j < 9; ++j) {
cin >> sudoku[i][j];
// 입력받은 수를 행, 열, 3x3 정사각형에 추가
row[i][sudoku[i][j]] = true;
col[j][sudoku[i][j]] = true;
block[i / 3][j / 3][sudoku[i][j]] = true;
if (sudoku[i][j] == 0) blank.push_back({ i, j });
}
recur(0);
return 0;
}
2. 비트 연산으로 구현
#include <bits/stdc++.h>
using namespace std;
int sudoku[9][9];
int row[9];
int col[9];
int block[3][3];
vector<pair<int, int>> blank;
void recur(int cur) {
if (blank.size() == cur) {
for (int i = 0; i < 9; ++i) {
for (int j = 0; j < 9; ++j) cout << sudoku[i][j] << ' ';
cout << '\n';
}
exit(0);
}
int x = blank[cur].first;
int y = blank[cur].second;
for (int i = 1; i < 10; ++i) {
int bit = (1 << i);
if ((row[x] & bit) || (col[y] & bit) || (block[x / 3][y / 3] & bit)) continue;
row[x] |= bit;
col[y] |= bit;
block[x / 3][y / 3] |= bit;
sudoku[x][y] = i;
recur(cur + 1);
row[x] &= (~bit);
col[y] &= (~bit);
block[x / 3][y / 3] &= (~bit);
sudoku[x][y] = 0;
}
}
int main() {
ios::ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
for (int i = 0; i < 9; ++i) for (int j = 0; j < 9; ++j) {
cin >> sudoku[i][j];
row[i] |= (1 << sudoku[i][j]);
col[j] |= (1 << sudoku[i][j]);
block[i / 3][j / 3] |= (1 << sudoku[i][j]);
if (sudoku[i][j] == 0) blank.push_back({ i, j });
}
recur(0);
return 0;
}
bit연산으로 구현하면 빨라질까 해서 구현해봤지만.. 아무래도 메모리접근 한번보다는 비트연산의 비용이 더 비싼 것 같다.
#include <bits/stdc++.h>
using namespace std;
int N, M;
string ans;
void recur(int prev, int cnt) {
if (cnt == M) {
ans.back() = '\n';
cout << ans;
return;
}
for (int cur = prev; cur <= N; ++cur) {
ans += cur + '0';
ans += ' ';
recur(cur, cnt + 1);
ans.pop_back();
ans.pop_back();
}
}
int main() {
ios::ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
cin >> N >> M;
recur(1, 0);
return 0;
}
