중복을 허락하지 않으면서 모든 경우를 뽑아야 하므로, 방문한 지점을 체크하는 배열을 활용한 백트레킹 기법으로 문제를 해결한다.
#include<iostream>
#include<vector>
using namespace std;
int n, m;
bool visited[9];
vector<int> v;
void bt(int);
int main(void) {
cin >> n >> m;
bt(0);
}
void bt(int cnt) {
if (cnt == m) {
for (int i = 0; i < m; i++)
cout << v[i] << ' ';
cout << '\n';
return;
}
for (int i = 1; i <= n; i++) {
if(!visited[i]){
visited[i] = true;
v.push_back(i);
bt(cnt + 1);
visited[i] = false;
v.pop_back();
}
}
}
각 라운드마다 가위, 바위, 보를 카운팅 한 후 각 경우마다 패배자를 Check해서 1명이 남을 때까지 라운드를 진행합니다.
#include<iostream>
#include<string>
using namespace std;
string list[11];
int main(void) {
ios::sync_with_stdio(false);
cin.tie(0);
int t;
cin >> t;
while (t--) {
int n;
cin >> n;
bool check[11] = {}; // i번째 선수가 졌으면 check[i] = true;
bool flag = false;
for (int i = 1; i <= n; i++)
cin >> list[i];
for (int i = 0; i < list[1].length(); i++) {
bool RPS[3] = {}; // R P S 나온걸체크
for (int j = 1; j <= n; j++) {
if (check[j] == true) // 이미 기존에 진사람
continue;
if (list[j][i] == 'R')
RPS[0] = true;
if (list[j][i] == 'P')
RPS[1] = true;
if (list[j][i] == 'S')
RPS[2] = true;
}
// R P S 가 다 나온 경우.
if (RPS[0] && RPS[1] && RPS[2])
continue;
// R P 가 나온 경우
if (RPS[0] && RPS[1] && !RPS[2]) {
for (int j = 1; j <= n; j++)
if (check[j] == false && list[j][i] == 'R')
check[j] = true;
}
// R S 가 나온 경우
if (RPS[0] && !RPS[1] && RPS[2]) {
for (int j = 1; j <= n; j++)
if (check[j] ==false && list[j][i] == 'S')
check[j] = true;
}
// P S 가 나온 경우
if (!RPS[0] && RPS[1] && RPS[2]) {
for (int j = 1; j <= n; j++)
if (check[j] == false && list[j][i] == 'P')
check[j] = true;
}
int count = 0, index = 0;
for (int j = 1; j <= n; j++) {
if (check[j] == false) {
count++;
index = j;
}
}
if (count == 1){
cout << index << '\n';
flag = true;
break;
}
}
if (!flag)
cout << 0 << '\n';
}
}
= 1번 나무에서 지금까지 떨어진 자두의 수 ( 방향 전환 없으므로 1번 나무에서 계속 있었다. )
dp[x][1][1] : x 초에 1번 방향을 전환했고 2번 나무 위치에서 최댓값.
= ( x - 1 초에서 0번 방향을 전환했고, 1번 나무 위치에서 최댓값 , x - 1 초에서 1번 방향을 전환했고,
2번 나 무 위치에서 최대값 ) 중 더 큰 값에 t[x] 가 2라면 + 1을 해준다.
-점화식
dp[x][y][0] = max(dp[x-1][y-1][1], dp[x-1][y][0]) 에 t[x] 가 1이라면 1을 더해준다.
dp[x][y][1] = max(dp[x-1][y-1][0], dp[x-1][y][1]) 에 t[x] 가 2라면 1을 더해준다.
#include<iostream>
#include<algorithm>
using namespace std;
int t[1001];
int n, m;
int dp[1001][31][2];
int main(void) {
ios::sync_with_stdio(false);
cin.tie(0);
// 입력
cin >> n >> m;
for (int i = 1; i <= n; i++) {
cin >> t[i];
}
// 초기값
for (int i = 1; i <= n; i++) {
dp[i][0][0] = dp[i - 1][0][0];
dp[i][1][1] = max(dp[i - 1][1][1], dp[i - 1][0][0]);
if (t[i] == 1)
dp[i][0][0]++;
if (t[i] == 2)
dp[i][1][1]++;
}
// 점화식
for (int i = 2; i <= n; i++) {
for (int j = 1; j <= m; j++) {
dp[i][j][0] = max(dp[i - 1][j - 1][1], dp[i - 1][j][0]);
dp[i][j][1] = max(dp[i - 1][j - 1][0], dp[i - 1][j][1]);
if (t[i] == 1)
dp[i][j][0]++;
else
dp[i][j][1]++;
}
}
int result = 0;
for (int j = 0; j <= m; j++)
for (int k = 0; k < 2; k++)
if (dp[n][j][k] > result)
result = dp[n][j][k];
cout << result;
}
가장 먼저 생각나는 방법은 모든 곳에서 DFS 탐색을 진행하며, 가장 오래 살아남는 값을 구하는 방법입니다.
단순하고 정확하지만 시간초과에 걸립니다.
따라서 DFS 탐색을 진행하며, 더 이상 탐색을 진행하지 않아도 되는 경우에 한해서는 가지치기를 해줘야 합니다.
이를 위해 메모이제이션을 이용합니다.
똑같이 모든 곳에서 DFS 탐색을 진행해나가는데, DFS 탐색을 하며 그 지점에서 가장 오래 살아남는 값을 저장해나갑니다.
그러다 이미 탐색이 완료된 지점(값을 저장한 곳)에 방문하게 되면 더 이상 탐색을 진행하지 않고도
가장 오래 살아남는 값을 도출해낼 수 있으므로 탐색을 종료하면 됩니다.
#include<iostream>
#include<algorithm>
using namespace std;
int n;
int map[500][500];
int dp[500][500];
int d_x[4] = { -1,0,1,0 };
int d_y[4] = { 0,-1,0,1 };
int DFS(int, int);
int main(void) {
cin >> n;
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
cin >> map[i][j];
int ans = 0;
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
ans = max(ans, DFS(i, j)); // 지금까지 나온 값 중 가장 큰 값을 저장.
cout << ans;
}
int DFS(int x, int y) {
if (dp[x][y]) // 이미 탐색이 완료된 지점이라면 종료
return dp[x][y];
dp[x][y] = 1; // 아니라면 1부터 탐색 진행.
for (int i = 0; i < 4; i++) {
int n_x = x + d_x[i], n_y = y + d_y[i];
if (0 <= n_x && n_x < n && 0 <= n_y && n_y < n)
if (map[x][y] < map[n_x][n_y])
dp[x][y] = max(dp[x][y], DFS(n_x, n_y) + 1);
}
return dp[x][y];
}
