void comb(int cnt, int start, vector<int> &archers) {
if (cnt == 3) {
int result = 0;
copyTmp();
for (int i = 0; i < n; i++) {
result += thisTurn(archers);
}
ans = max(ans, result);
return;
}
for (int i = start + 1; i < m; i++) { //m이 가로 길이
archers.push_back(i);
comb(cnt + 1, i, archers);
archers.pop_back();
}
}
backtracking을 사용하며 가능한 모든 궁수 3명의 조합을 찾을 수 있습니다.
조합이 완성되면 게임을 진행하며 총 몇명의 적(result)이 제거 되었는지 카운트 합니다.
thisTurn()은 한 턴에서 제거된 적을 계산하며, 한 게임은 세로길이는 n턴이 지나야 게임이 끝나므로 n번 반복합니다.
2. 조합이 완성되었을 때, 궁수 각자의 표적을 찾는다.
int thisTurn(vector<int> &archers) {
int cnt = 0;
vector <pair<int, int>> targets;
for (int i = 0; i < archers.size(); i++) {
pair<int, int> target = decideTarget(archers[i]);
if (target.first != 999 && target.second != 999) {
targets.push_back(target);
}
}
for (int i = 0; i < targets.size(); i++) {
pair<int, int> target = targets[i];
if (tmp[target.first][target.second] == 1) {
tmp[target.first][target.second] = 0;
cnt++;
}
}
for (int i = n - 2; i >= 0; i--)
for (int j = 0; j < m; j++)
tmp[i + 1][j] = tmp[i][j];
for (int j = 0; j < m; j++)
tmp[0][j] = 0;
return cnt;
}
궁수 한명의 표적을 찾는 일은 decideTarget()에서 진행됩니다. 제거할 모든 적을 vector<pair<int, int>> targets에 저장한 뒤 적을 제거하며 cnt를 카운트합니다. 이렇게 한턴이 종료 되면 적들을 한칸 씩 밑으로 이동 시킵니다.
3. pair<int, int> decideTarget(int archer)
pair<int, int> decideTarget(int archer) {
bool visited[15][15] = { false };
pair<int, int> nextdir[3] = { {-1,0}, {0,1}, {0,-1} };
pair<int, int> ret = { 999, 999 };
queue<coord> q;
int dist = 999;
q.push({ n - 1, archer, 1 });
while (!q.empty()) {
coord now = q.front();
q.pop();
if ((dist != 999 && dist < now.dist) || now.dist > d) //이미 표적을 잡았는데 더 멀리 갈때, 공격 범위를 벗어 낫을 때
break;
if (tmp[now.x][now.y] == 1) {
if (dist >= now.dist) {
dist = now.dist;
if(ret.second > now.y) //기존 표적보다 더 왼쪽에 있을 때
ret = { now.x, now.y };
}
}
for (int j = 0; j < 3; j++) {
int next_x = now.x + nextdir[j].first;
int next_y = now.y + nextdir[j].second;
if (0 <= next_x && next_x < n && 0 <= next_y && next_y < m) {
if (!visited[next_x][next_y]) {
visited[next_x][next_y] = true;
q.push({ next_x, next_y, now.dist + 1 });
}
}
}
}
return ret;
}
궁수 한명이 표적을 찾는 함수입니다. 가장 짧은 거리의 적을 표적으로 삼는 조건이 있기 때문에 DFS보다 BFS가 적합하다고 판단하였습니다.
소스 코드
#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
using namespace std;
int map[15][15];
int tmp[15][15];
int n, m, d;
int ans = 0;
typedef struct coord {
int x;
int y;
int dist;
};
void copyTmp() {
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++)
tmp[i][j] = map[i][j];
}
pair<int, int> decideTarget(int archer) {
bool visited[15][15] = { false };
pair<int, int> nextdir[3] = { {-1,0}, {0,1}, {0,-1} };
pair<int, int> ret = { 999, 999 };
queue<coord> q;
int dist = 999;
q.push({ n - 1, archer, 1 });
while (!q.empty()) {
coord now = q.front();
q.pop();
if ((dist != 999 && dist < now.dist) || now.dist > d) //이미 표적을 잡았는데 더 멀리 갈때, 공격 범위를 벗어 낫을 때
break;
if (tmp[now.x][now.y] == 1) {
if (dist >= now.dist) {
dist = now.dist;
if(ret.second > now.y) //기존 표적보다 더 왼쪽에 있을 때
ret = { now.x, now.y };
}
}
for (int j = 0; j < 3; j++) {
int next_x = now.x + nextdir[j].first;
int next_y = now.y + nextdir[j].second;
if (0 <= next_x && next_x < n && 0 <= next_y && next_y < m) {
if (!visited[next_x][next_y]) {
visited[next_x][next_y] = true;
q.push({ next_x, next_y, now.dist + 1 });
}
}
}
}
return ret;
}
int thisTurn(vector<int> &archers) {
int cnt = 0;
vector <pair<int, int>> targets;
for (int i = 0; i < archers.size(); i++) {
pair<int, int> target = decideTarget(archers[i]);
if (target.first != 999 && target.second != 999) {
targets.push_back(target);
}
}
for (int i = 0; i < targets.size(); i++) {
pair<int, int> target = targets[i];
if (tmp[target.first][target.second] == 1) {
tmp[target.first][target.second] = 0;
cnt++;
}
}
for (int i = n - 2; i >= 0; i--)
for (int j = 0; j < m; j++)
tmp[i + 1][j] = tmp[i][j];
for (int j = 0; j < m; j++)
tmp[0][j] = 0;
return cnt;
}
void comb(int cnt, int start, vector<int> &archers) {
if (cnt == 3) {
int result = 0;
copyTmp();
for (int i = 0; i < n; i++) {
result += thisTurn(archers);
}
ans = max(ans, result);
return;
}
for (int i = start + 1; i < m; i++) { //m이 가로 길이
archers.push_back(i);
comb(cnt + 1, i, archers);
archers.pop_back();
}
}
void solve() {
vector<int> archers;
comb(0, -1, archers);
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> n >> m >> d;
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++)
cin >> map[i][j];
solve();
cout << ans;
}
3. cnt < k 라면 mid가 더 큰 수여야 한다는 뜻이고, cnt >= k 라면 더 작은 수 이거나 현재 조건을 만족한다는 의미이다.
1번
과정은 start=1, end=k, mid = (start+end)/2로 잡는다. end = k인 이유는 k보다 작은 숫자는 적어도 k개 보다 많거나 같기 때문이다.
2번
cnt를 구하는 과정이 떠올리기에 어려울 수 있다. 하단의 코드를 보며 차근 차근 따라가보자
long long countNum(long long mid) {
long long cnt = 0;
for (int i = 1; i <= n; i++) {
cnt += min( mid/i, n);
}
return cnt;
}
만약 n=4, mid = 8이라면
1
2
3
4
2
4
6
8
3
6
9
12
4
8
12
16
이러한 모양일 것이다.
즉, i행은 i*1, i*2, i*3, ..의 숫자들로 이루어져 있고, i행의 숫자들 중 mid보다 작거나 같은 숫자는
(i*j <= m)를 만족하는 j의 개수이고 이는 i*1, i*2, ..., i*j이므로, mid/i와 같은 값이 된다. 하지만 mid/i가 n을 초과할 경우
i행의 cnt=n이 될 것이다.
소스 코드
#include <iostream>
#include <algorithm>
using namespace std;
long long n, k;
long long countNum(long long mid) {
long long cnt = 0;
for (int i = 1; i <= n; i++) {
cnt += min( mid/i, n);
}
return cnt;
}
long long search() {
long long end = k;
long long start = 1;
long long result = 0;
while (start <= end) {
long long mid = (start + end) / 2;
long long cnt = countNum(mid); //mid보다 작거나 같은 갯수
if (cnt < k) {
start = mid + 1;
}
else {
result = mid;
end = mid - 1;
}
}
return result;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> n >> k;
cout << search();
}
일단 문제를 보자마자 떠오른 것은 DP를 사용해야겠다는 것이다. 처음 top-down방식으로 해결하였으나, 재귀가 깊어져서 인지 메모리 제한에 걸렸다. 그래서 bottom-up방식을 사용하여 다시 해결했다.
동적계획법을 사용하는 핵심 코드이다.
for (int i = 0; i < map[now].size(); i++) {
int next = map[now][i];
if (--indegree[next] == 0) {
q.push(next);
}
dp[next] = max(dp[next], dp[now] + buildtime[next]);
}
예를 들어 a를 짓기 위해 b와 c 두 건물이 모두 지어져야 한다면, b와 c둘 중 짓는대 까지 걸리는 시간 중 큰 값을 사용하여 현재 건물을 짓는 시간을 더하여 갱신 해주었다. 이 부분만 잘 이해한다면 크게 어려울 것은 없을 것이다.
소스 코드
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <string.h>
using namespace std;
int buildtime[1001];
int dp[1001];
int indegree[1001];
vector<int> map[1001];
int t, n, k, dest;
void init() {
memset(buildtime, 0, sizeof(buildtime));
memset(dp, 0, sizeof(dp));
memset(indegree, 0, sizeof(indegree));
for (int i = 0; i <= n; i++) {
map[i].clear();
}
cin >> n >> k;
for (int i = 1; i <= n; i++) {
cin >> buildtime[i];
}
for (int i = 0; i < k; i++) {
int a, b;
cin >> a >> b;
map[a].push_back(b);
indegree[b]++;
}
cin >> dest;
}
int solve(int dest) {
int result = 0;
queue <int> q;
for (int i = 1; i <= n; i++)
if (indegree[i] == 0) {
q.push(i);
dp[i] = buildtime[i];
}
while (!q.empty()) {
int now = q.front();
q.pop();
if (now == dest) {
result = dp[now];
break;
}
for (int i = 0; i < map[now].size(); i++) {
int next = map[now][i];
if (--indegree[next] == 0) {
q.push(next);
}
dp[next] = max(dp[next], dp[now] + buildtime[next]);
}
}
return result;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> t;
while (--t >= 0) {
init();
cout << solve(dest) << "\n";
}
}
for (int i = 0; i < m; i++) {
int a, b;
cin >> a >> b;
v[a].push_back(b);
indegree[b]++;
}
위상정렬은 자신이 무엇인가를 하기 위해 다른 무엇인가가 완료되어야 할 수 있다?
즉, 어떤 일을 하는 순서를 찾는 알고리즘 입니다.
예를 들어, '그냥 기초'를 하기 위해선 완전 기초가 요구되어야 하며, '어려움'을 위해서는 '그냥 기초'가 수행되어야 하고,
'보통'을 위해서는 '완전 기초'와 '진짜 기초'가 모두 수행되어야 합니다. 여기서 indegree는 어떤 노드가 수행되기 위해, 선 수행되어야 하는 노드의 수 입니다. 위의 경우 indegree[완전기초] = 0 , indegree[그냥기초] = 1 , indegree[보통] = 2로 표현 가능합니다.
2. q에 초기값 담기
queue<int> q;
for (int i = 1; i <= n; i++) {
if (indegree[i] == 0)
q.push(i);
}
그럼 가장 먼저 수행가능 한 노드는 어떤 것 일까요? indegree[] = 0인 값들, 즉 자신이 수행되기 위해 선 수행 할 것이 없는 것들입니다. 그러한 값을 q에 담아줍니다.
3. q의 값을 pop하며, 조건에 해당하는 값을 push
while (!q.empty()) {
int now = q.front();
q.pop();
cout << now << " ";
for (int i = 0; i < v[now].size(); i++) {
if (--indegree[v[now][i]] == 0) {
q.push(v[now][i]);
}
}
}
자 이제 q에서 pop한 값을 now라 한다면, 자신을 수행하기 위해 now가 선 수행되어야하는 노드들의 indegree가 줄어들 것이고, indegree가 0이 된다면 선 수행할 것들이 없다는 의미이므로 q에 담아줍니다.
소스 코드
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
vector<int> v[32001];
int indegree[32001];
int n, m;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> n >> m;
for (int i = 0; i < m; i++) {
int a, b;
cin >> a >> b;
v[a].push_back(b);
indegree[b]++;
}
queue<int> q;
for (int i = 1; i <= n; i++) {
if (indegree[i] == 0)
q.push(i);
}
while (!q.empty()) {
int now = q.front();
q.pop();
cout << now << " ";
for (int i = 0; i < v[now].size(); i++) {
if (--indegree[v[now][i]] == 0) {
q.push(v[now][i]);
}
}
}
}
1. 기본적으로 재귀 함수를 사용하여 괄호 추가가 가능한 모든 경우의 수에 대해 탐색하였고, 연산자와 숫자를 따로 분리하여 관리 하였다.
괄호 추가가 가능한 모든 경우의 수를 탐색하는 코드이다.
void solve(int now) {
for (int i = now; i < numbers.size() - 1; i++) {
if (visited[i] == false) {
visited[i] = visited[i + 1] = true;
ans = max(ans, calc_result());
solve(i + 1);
visited[i] = visited[i + 1] = false;
}
}
}
visited[]는 괄호에 감싸져 있는 숫자를 체크하는 배열이다. 문제의 조건에서 괄호안에는 하나의 연산자만 포함한다고 했으므로, 인접한 두 숫자에 대해서 방문체크를 하게 된다. 이후 calc_result()라는 함수안에서 현제 괄호를 포함한 전체 수식을 계산하게 된다.
calc_result()
long long calc_result() {
vector <long long> tmpnumbers;
vector <char> tmptokens;
vector <bool> visited_t(tokens.size());
long long result;
//괄호 값 먼저 계산
for (int i = 0; i < numbers.size(); i++) {
if (i < numbers.size() -1 && visited[i] && visited[i + 1]) {
tmpnumbers.push_back(part_calc(numbers[i], numbers[i + 1], tokens[i]));
visited_t[i] = true;
i += 1;
}
else
tmpnumbers.push_back(numbers[i]);
}
//괄호에서 사용하고 남은 연산자 배열
for (int i = 0; i < tokens.size(); i++)
if (!visited_t[i])
tmptokens.push_back(tokens[i]);
//괄호의 계산이 종료 된 이후, 전체 수식 계산
result = tmpnumbers[0];
for (int i = 1; i < tmpnumbers.size(); i++)
result = part_calc(result, tmpnumbers[i], tmptokens[i - 1]);
return result;
}
괄호값을 먼저 계산하여 수를 정리하고, 괄호안에서 사용된 연산자를 제외한 연산자를 모아 다시 수식 생성
앞서 visited[]를 통해 괄호의 위치를 체크하였기 때문에 괄호가 포함된 (a ,(+-*), b)를 part_calc() 함수에서 계산하며,
괄호안에서 사용된 연산자를 visited_t[]로 사용표시를 한다. 또한 괄호가 정리된 이후 계산 될 새로운 숫자 벡터 tmpnumbers에 push한다.
tmpnumbers={1, 5, 9} -> 2와3 사이의 '+'위치 체크, 4와5 사이의 '+'위치 체크, visited_t[1]=visited_t[3]=true
2. 괄호에 포함되지 않아 사용되지 않은 연산자를 tmptokens에 담는다.
tmptokens={-, -}
3. 정리된 전체 수식을 계산한다.
소스 코드
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int n;
vector <long long> numbers;
vector <char> tokens;
bool visited[20];
long long ans = -9999999999;
long long part_calc(long long a, long long b, char token) {
long long result = 0;
if (token == '*')
result = a * b;
else if (token == '+')
result = a + b;
else if (token == '-')
result = a - b;
return result;
}
long long calc_result() {
vector <long long> tmpnumbers;
vector <char> tmptokens;
vector <bool> visited_t(tokens.size());
long long result;
for (int i = 0; i < numbers.size(); i++) {
if (i < numbers.size() -1 && visited[i] && visited[i + 1]) {
tmpnumbers.push_back(part_calc(numbers[i], numbers[i + 1], tokens[i]));
visited_t[i] = true;
i += 1;
}
else
tmpnumbers.push_back(numbers[i]);
}
for (int i = 0; i < tokens.size(); i++)
if (!visited_t[i])
tmptokens.push_back(tokens[i]);
result = tmpnumbers[0];
for (int i = 1; i < tmpnumbers.size(); i++)
result = part_calc(result, tmpnumbers[i], tmptokens[i - 1]);
return result;
}
void solve(int now) {
for (int i = now; i < numbers.size() - 1; i++) {
if (visited[i] == false) {
visited[i] = visited[i + 1] = true;
ans = max(ans, calc_result());
solve(i + 1);
visited[i] = visited[i + 1] = false;
}
}
}
int main() {
cin >> n;
for (int i = 0; i <= n/2; i++) {
int num;
char token;
scanf("%1d", &num);
numbers.push_back(num);
if (n / 2 != i) {
scanf("%c", &token);
tokens.push_back(token);
}
}
solve(0);
if (n == 1)
cout << numbers[0];
else
cout << ans;
}
