수열을 문자열을 이용하여 나타내고, substr 함수를 이용하여 문제의 조건을 확인해줄 수 있다.
숫자를 붙여나가는 과정을 1, 2, 3의 순서대로 붙여나간다면 사전순으로 가장 빠른 가장 긴 문자열을 알아낼 수 있다.
물론 숫자를 붙여나가다가 "나쁜 수열"을 만난다면 그 이후는 더 탐색할 필요가 없으므로 되돌아나오자.
개수가 80개로 전체를 탐색하기에는 나올 수 있는 경우의 수가 너무 많지만(3^80), "나쁜 수열"의 비중이 매우 높아 가지치기가 매우 잘 되므로 수열 자체는 빠르게 얻어낼 수 있다.
물어볼 수 있는 개수가 80개 뿐이므로, 글쓴이는 답이 될 80개의 문자열을 코드를 이용하여 뽑아내고 이를 이용하여 O(1)에 답을 하는 코드를 제출하였다.
아래는 답의 배열을 뽑아내기 위한 전처리 코드이다. 이 코드 자체는 원하는 결과를 모두 찾은 뒤 탐색을 종료하는 구현이 되어있지 않으므로 동작시간이 오래 걸린다는 점을 유의하자. 또한, 아래 코드는 출력된 값의 마지막 항 뒤에 ','가 같이 출력하고 0번째 항은 생략하고 있는 점을 유의하자.
#include <iostream>
#include <string>
using namespace std;
bool done[81];
string ans[81];
string s = "";
void func(int current) {
for (int k = 1; k <= 3; k++) {
s += to_string(k);
bool chk = 1;
for (int i = 1; i * 2 <= current; i++) {
if (s.substr(current - i, i) == s.substr(current - 2 * i, i)) chk = 0;
}
if (chk) {
if (!done[current]) {
done[current] = 1;
ans[current] = s;
if (current == 80) {
cout << '{';
for (int i = 1; i <= 80; i++) cout << '"' << ans[i] << "\", ";
cout << '}';
}
}
if (current!=80) func(current + 1);
}
s.pop_back();
}
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
func(1);
}
과제를 수행하는 날짜를 뒷날짜부터 살펴보며, 그날 수행할 수 있는 가장 점수가 높은 과제를 수행하는 것이 최적이 된다. 증명은 귀류법으로 간단히 할 수 있다.
우선순위 큐(priority queue)를 이용하면 현재 날짜에 수행할 수 있는 가장 점수가 높은 과제가 무엇인지를 쉽게 관리할 수 있다.
아래는 제출한 소스코드이다.
#include <iostream>
#include <queue>
using namespace std;
queue<int> que[1001];
priority_queue<int> pq;
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
int ans = 0;
int N; cin >> N;
while (N--) {
int d, w; cin >> d >> w;
que[d].push(w);
}
for (int i = 1000; i > 0; i--) {
while (!que[i].empty()) {
pq.push(que[i].front());
que[i].pop();
}
if (!pq.empty()) {
ans += pq.top();
pq.pop();
}
}
cout << ans;
}
주어지는 지형에서 가장 왼쪽 열에서 오른쪽 열까지 이을 수 있는 파이프의 개수를 세는 문제이다.
이 문제는 왼쪽 열의 가장 위칸서부터 출발하여 오른쪽 열로 도달할 수 있는지를 확인하면서 방문한 칸을 다시 방문하지 못하게 처리하는 것으로 문제를 해결할 수 있다.
이러한 방식이 통하는 이유는 각 칸을 이번 시도에 방문하여 오른쪽 열에 도달할 수 없다면 다른 시도에서 다시 방문하더라도 오른쪽 끝으로 갈 수 없기 때문이다. (또한, 도달했다면 모든 파이프가 지나는 칸은 달라야한다는 조건에 따라 해당 칸을 다시 이용할 수 없고, 가장 위칸서부터 출발한 이 경로로 이동하면 같은 칸을 경유하는 다른 경로에 비해 존재할 수 있는 다른 가능한 가능성을 배제하지 않는다는 점을 생각하자.)
아래는 제출한 소스코드이다.
#include <iostream>
#include <string>
using namespace std;
int R, C;
string field[10002];
int dfs(int r, int c) {
if (c == C - 1) return 1;
if (field[r - 1][c + 1] == '.') {
field[r - 1][c + 1] = 'x';
if (dfs(r - 1, c + 1)) return 1;
}
if (field[r][c + 1] == '.') {
field[r][c + 1] = 'x';
if (dfs(r, c + 1)) return 1;
}
if (field[r + 1][c + 1] == '.') {
field[r + 1][c + 1] = 'x';
if (dfs(r + 1, c + 1)) return 1;
}
return 0;
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> R >> C;
for (int c = 0; c < C; c++) field[0] += 'x';
for (int c = 0; c < C; c++) field[R + 1] += 'x';
for (int r = 1; r <= R; r++) cin >> field[r];
int ans = 0;
for (int r = 1; r <= R; r++) {
ans += dfs(r, 0);
}
cout << ans;
}