동적계획법으로 풀었다. 메모리는 따로 사용하지 않았고 주어진 이차원 벡터에 그대로 덮어썼다.
(i행 0열)에 왔다는 것은 i - 1행에서는 0열이 아닌 1열 또는 2열 또는 3열을 거쳤다는 것이기 때문에 (i행 0열)의 값에 (i - 1행 1열), (i - 1행 2열), (i - 1행 3열) 중 최댓값을 더해주었다. 그러면 land[i][0]에는 i행 0열까지 오는 경로 중 가장 최댓값을 가질 수 있는 경로로 왔을 때의 점수가 저장되어있는 것이다. 그런식으로 누적해서 더해서 land[마지막 행]에는 각 열의 최댓값 4개가 저장되어 있다. (4열이기 때문) 그 4개의 숫자 중에서 최댓값이 정답이 된다.
#include <iostream>
using namespace std;
int main() {
int n, m;
cin >> n >> m;
int num = 1;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (j == m - 1)
cout << num++ << '\n';
else
cout << num++ << " ";
}
}
return 0;
}
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int n;
cin >> n;
vector<int> v(n);
for (int i = 0; i < v.size(); i++) {
cin >> v[i];
}
sort(v.begin(), v.end());
int m;
cin >> m;
vector<bool> result(m);
for (int i = 0; i < m; i++) {
int temp;
cin >> temp;
result[i] = binary_search(v.begin(), v.end(), temp);
}
for (int i = 0; i < m; i++) {
cout << result[i] << " ";
}
return 0;
}
벡터에 일단 1~N을 저장해놓고 직접 지워가며 시뮬레이션하며 풀었다. 이 과정을 벡터가 빌 때까지 반복해주었다.
원형 연결리스트처럼 동작하게 하기 위해 modulo 연산을 사용해주었다.
#include <iostream>
#include <vector>
using namespace std;
int main() {
int n, k;
cin >> n >> k;
vector<int> v(n);
for (int i = 0; i < n; i++) {
v[i] = i + 1;
}
vector<int> result;
int start = 0;
while (!v.empty()) {
int index = (start + k - 1) % v.size();
result.push_back(v[index]);
v.erase(v.begin() + index);
if(!v.empty())
start = index % v.size();
}
cout << "<";
for (int i = 0; i < result.size(); i++) {
cout << result[i];
if (i == result.size() - 1) {
cout << ">";
}
else {
cout << ", ";
}
}
return 0;
}
start 변수는 K번째를 세기 시작하는 곳이다. start부터 K번째 위치를 지우면 된다.
그런데 지우고 나서가 문제이다. start로부터 K번째 위치가 index라고 하면 지우고 나서 이 위치가 start가 되면 안 된다.
예를 들어 벡터의 크기가 8이었다고 하자. 그리고 start가 5, K가 3이어서 지워야 할 위치인 index가 7이었다고 하자. 그래서 인덱스가 7인 원소를 삭제했다고 하자. 그러면 벡터의 크기는 8에서 7로 줄어드는데 그러면 인덱스 7은 벡터의 범위를 벗어났으므로 index out of range 에러가 날 것이다. 따라서 현재 vector 크기로 한 번 더 modulo 연산을 해줘야 한다.
최단경로를 구하는 것이기 때문에 BFS(너비 우선 탐색)로 풀면 된다. 가중치가 없는 그래프에서 최단경로를 구하라고 하면 무조건 BFS이다. 이 지도에서는 상하좌우 어디든 비용이 1이므로 가중치가 없다고 할 수 있다.
일단 코드는 다음과 같다.
#include <iostream>
#include <vector>
#include <queue>
#include <tuple>
using namespace std;
int main() {
int n, m;
cin >> n >> m;
vector<vector<char>> map(n, vector<char>(m));
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
cin >> map[i][j];
}
}
int maxDistance = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (map[i][j] == 'L') {
queue<tuple<int, int, int>> q;
vector<vector<bool>> visited(n, vector<bool>(m));
q.push(make_tuple(i, j, 0));
while (!q.empty()) {
tuple<int, int, int> cur = q.front();
q.pop();
int row = get<0>(cur);
int col = get<1>(cur);
if (!visited[row][col]) {
if (get<2>(cur) > maxDistance)
maxDistance = get<2>(cur);
visited[row][col] = true;
if (row + 1 < n && map[row + 1][col] == 'L' && !visited[row + 1][col]) {
q.push(make_tuple(row + 1, col, get<2>(cur) + 1));
}
if (row - 1 >= 0 && map[row - 1][col] == 'L' && !visited[row - 1][col]) {
q.push(make_tuple(row - 1, col, get<2>(cur) + 1));
}
if (col + 1 < m && map[row][col + 1] == 'L' && !visited[row][col + 1]) {
q.push(make_tuple(row, col + 1, get<2>(cur) + 1));
}
if (col - 1 >= 0 && map[row][col - 1] == 'L' && !visited[row][col - 1]) {
q.push(make_tuple(row, col - 1, get<2>(cur) + 1));
}
}
}
}
}
}
cout << maxDistance;
return 0;
}
육지인 칸이라면 매 칸마다 BFS를 하면 된다. BFS를 하기 위해 큐를 사용했고 큐에는 tuple 객체를 만들어 넣어주었다.
튜플의 첫 번째 원소는 행, 두 번째 원소는 열, 세 번째 원소에는 BFS를 시작한 그 칸에서 여기까지의 거리를 저장해주었다. 그리고 최대 거리를 maxDistance에 저장하며 갱신해주었다.
상하좌우를 탐색하기만 하면 된다. 다른 BFS와 조금 다른 점은 보통 BFS는 특정 지점에서 특정 지점으로 가는 최단경로를 구하는 것이기 때문에 visited 배열도 하나만 필요했고 다 공유했다. 하지만 이 문제에서는 특정 지점에서 특정 지점으로 가는 것이 아니라 어느 지점인지 모르는 지점에서 어느 지점인지 모르는 지점까지의 최단경로 중 최장경로를 찾는 것이기 때문에 모든 육지에서 나머지 육지로 가는 모든 경우의 수를 구해야 한다. 따라서 한 칸마다 BFS를 새로 시작하기 때문에 매 칸마다 그 칸을 위한 visited 배열도 새로 만들고 queue도 새로 만들어줘야 한다.
