동적계획법으로 풀었다. 메모리는 따로 사용하지 않았고 주어진 이차원 벡터에 그대로 덮어썼다.
(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 연산을 해줘야 한다.
