2020.06.05 팀연습 set
19시 15분 ~ 21시 15분, 총 2시간 진행
나 혼자 팀, 윤제-지환 팀, 관우네팀, ainch님네 팀
11문제 중, 9문제 AC
[ 간단 후기 ]
A - 단순 구현 문제 / 문제에서 시킨대로 따라가면 해결 가능
B - 깔끔한 수학 문제 / 그냥 곱하고 더하고 하면 된다
C - 이것도 단순 구현 문제 / 제한을 잘못 보고 열심히 계산해서도 풀 수 있는 문제 ㅎ
D - 대회 중에는 문제를 잘못 이해한 것 같지만 더러워보여서 넘어갔었다 / 실제로 생각하기는 쉽게 생각했지만 구현이 귀찮았다;;
E - 대놓고 디피
F - 이분 탐색도 가능하지만 다익느낌으로도 가능한 문제 / 약간 다익을 생각하고 풀었는데 정확히 다익이라고 하기 뭐하면서 안그러면서 음
G - 이분 탐색 문제로 너무 깔끔한데 아직도 이분 탐색을 바로 알아채지 못한다... 이분 탐색 문제 좀 풀어야지;
H - 그리디? 이런식의 데이터 만드는 문제 싫어하는데 그래도 깔끔했음
I - 딱 그리디!
J - 다익 문제..
K - 구간 xor 문제 / 세그로 풀었는데 굳이? 그냥 prefix sum으로 해결 가능
총평 - 지환이형이 디비 실습을 듣는다해서 집에서 대기했는데..... 갑자기 개인전을 하자더니 지환이형이 수업 안듣는다고 나빼놓고 둘이 팀했다... ㅡㅡ / 그래도 문제가 잘 읽히고 풀이가 간단간단해서 빨리 풀 수 있었다 / 캡쳐상에서는 2등이지만 원래 2시간 약속을 하고 진행했었어서 그 때까진 내가 1등이다 ㅎㅋ / 팀적으론 아쉽지만 개인적으로 기분 좋았음 / 아무래도 대학 대회인만큼 문제가 많이 어렵진 않았다 / 근데 beginner division도 있는데 advanced가 좀 너무 쉬운느낌..?
백준 대회 문제집 https://www.acmicpc.net/category/detail/2123
공식 사이트 (문제셋 / 솔루션 x) https://hcpc.hanyang.ac.kr/contest_result/
A. 과제는 끝나지 않아!
[ 문제 설명 ]
이번 학기는 N분이고, 성애는 학기 중간중간 나오는 과제를 해결한다.
$ (\;1\leq N\leq1,000,000\;) $
과제는 완료해야 점수를 받을 수 있으며, 각 과제는 T분동안 진행해야 만점인 A점을 받을 수 있다.
$ ( \; 1 \leq A \leq 100 \;\; , \;\; 1 \leq T \leq 1,000,000 \; ) $
과제를 진행하는 규칙은 다음과 같다.
1. 과제는 최근에 나온 순서대로 한다. 또한 과제를 받으면 바로 시작한다.
2. 과제를 하던 더중 새로운 과제가 나온다면, 하던 과제를 중단하고 새로운 과제를 진행한다.
3. 새로운 과제가 끝났다면, 이전에 하던 과제를 이전에 하던 부분부터 이어서 한다.
[ 풀이 ]
우선, 과제는 가장 최근의 과제, 즉 가장 마지막에 나온 과제를 먼저 진행한다.
LIFO 구조인 스택을 쓰면 딱 맞을 것 같다.
스택을 이용해서 과제를 하다가 새로운 과제가 들어오면 저장해놓자
전체 학기의 시간이 백만밖에 안되므로 시간만큼 반복문을 돌리면서 과제를 마무리하는데 드는 시간을 1씩 줄이고 다 줄이면 그 과제의 점수를 더해주자
[ 코드 ]
// BOJ 17952 과제는 끝나지 않아!
// stack
#include <iostream>
#include <stack>
#include <algorithm>
using namespace std;
using pii = pair<int, int>;
int main() {
int n; cin >> n;
stack<pii> q;
pii cur = pii(-1, -1); // 현재 과제를 관리할 변수
int ans = 0;
for (int i = 1; i <= n; ++i) {
int x; cin >> x;
// 새로운 과제가 나온 경우
if (x == 1) {
// 하던 과제가 있다면 스택에 담기
if (cur.first != -1) q.push(cur);
int a, t; cin >> a >> t;
cur = pii(a, t - 1);
}
// 과제가 나오지 않은 경우
else {
if (cur.first == -1) continue;
else cur.second--;
}
// 현재 하던 과제를 마무리한 경우
if (cur.second == 0) {
ans += cur.first;
if (q.size()) cur = q.top(), q.pop();
else cur = pii(-1, -1);
}
}
cout << ans;
}
B. 스노우볼
[ 문제 설명 ]
H cm의 과제산의 각 i 높이의 위치에서 스노우볼이 $C_i$개만큼 1의 크기로 생긴다
$ ( \; 1 \leq H \leq 10^6 \;\; , \;\; 1 \leq i \leq H \;\; , \;\; 0 \leq C_i \leq 100 \; ) $
스노우볼은 1 cm 내려올 때마다 x 배만큼 커진다.
$ ( \; 1 \leq x \leq 100 \; ) $
스노우볼이 모두 내려왔을 때, 그 크기들의 합을 구하여라
[ 풀이 ]
단순히 계산해보면 i cm 에서 생긴 스노우볼은 굴러 내려왔을 때, $x^i$ 크기를 갖는다.
그 때, 크기들의 합은 다음 식으로 구할 수 있다.
$$ C_1 * x^1 + C_2 * x^2 + ... + C_H * x^H $$
물론 그 개수가 너무 많아서 $10^9 + 7$로 나눈 나머지를 출력해야하므로 그때그때 모듈로 처리를 해주자
[ 코드 ]
// BOj 17950 스노우볼
// 수학
#include <iostream>
#include <algorithm>
using namespace std;
using ll = long long;
const ll mod = 1e9 + 7;
int main() {
ll h, x; cin >> h >> x;
ll ans = 0, mul = x;
for (int i = 1; i <= h; ++i) {
ll c; cin >> c;
ans = (ans + c * mul) % mod;
mul = (mul * x) % mod;
}
cout << ans;
}
C. 퐁당퐁당 2
[ 문제 설명 ]
N명의 사람이 있고 "혼자 왔어요~" 술게임을 한다.
$ ( \; 1 \leq N \leq 1,000 \; ) $
1~N번 사람은 반 시계방향으로 있고, 1번 사람의 왼쪽 팔부터 시작해서 반시계방향으로 돌아간다.
들어야 하는 팔의 수는 1 부터 2 * N 까지 늘어나고 2 * N 이 되면 다시 1 까지 내려오고 이를 반복한다.
N명의 사람은 모두 게임을 너무 잘해서 재미가 없던 휘수는 트롤을 하려고 한다.
휘수는 P번 사람이며 T번째 순서에 고의적으로 손을 들지 않을 예정이다.
$ ( \; 1 \leq P \leq N \;\; , \;\; 1 \leq T \leq 10,000,000 \; ) $
T번째 순서에 휘수가 손을 들지 않아서 술을 먹을 수 있는지 출력하라
[ 풀이 ]
A번 문제와 비슷하게 휘수의 턴이 최대 천만밖에 안되므로 그냥 시뮬레이션을 돌리면 된다.
1 ~ N 명의 사람의 팔에 번호를 부여하자
1번 사람 -> 왼팔 : 0, 오른팔 : 1
2번 사람 -> 왼팔 : 2, 오른팔 : 3
...
N번 사람 -> 왼팔 : 2N - 2, 오른팔 : 2N - 1
이런 식으로 번호를 부여하면 시작은 0번부터 이다.
T번째 순서에 올릴 팔의 수와 시작 번호를 알 수 있다면 그 팔 중에 휘수의 팔이 있는지 체크하면 된다.
[ 코드 ]
// BOJ 17938 퐁당퐁당 2
// 수학
#include <iostream>
using namespace std;
int main() {
int n, pos, t; cin >> n >> pos >> t;
pos--;
// 휘수의 양쪽 팔 번호
int h1 = pos * 2, h2 = pos * 2 + 1;
int hands = 1, ud = 1, st = 0, mod = 2 * n;
for (int i = 1; i < t; ++i) {
st = (st + hands) % mod;
// 올릴 팔의 수는 1~2N 을 왔다갔다
if (ud) {
if (hands == mod) {
hands--;
ud = !ud;
}
else hands++;
}
else {
if (hands == 1) {
hands++;
ud = !ud;
}
else hands--;
}
}
// T번째 턴에는 st 번호 부터 시작, hands 개의 팔 올릴 예정
for (int j = 0; j < hands; ++j) {
int cur = (j + st) % mod;
if (cur == h1 || cur == h2) {
cout << "Dehet YeonJwaJe ^~^";
return 0;
}
}
cout << "Hing...NoJam";
}
D. 목장 CCTV
[ 문제 설명 ]
준호는 N행 M열의 목장에 양이 NM마리 키우고 있다.
$ ( \; 1 \leq N \; , \; M \; 500 \; ) $
준호는 다른 지역에 가있는 동안 양을 지켜보기 위해 CCTV를 설치했고 CCTV는 설치 위치로부터 아래로 R행, 오른쪽으로 C열을 촬영한다.
CCTV가 촬영한 사진은 해당 영역에서 가장 큰 크기의 양의 사진이다.
또한, 양들은 준호가 없는 기간동안 상/하/좌/우 한 방향을 선택해 매일 1칸씩 이동한다.
다음 질문이 Q번 들어올 때, 질문에 대한 답을 구하여라.
$ ( \; 1 \leq Q \leq 50,000 \; ) $
CCTV의 시작 지점, 크기 R과 C가 주어진다. 또한, 준호가 없는 기간이 주어지고, 양이 이동하는 방향이 주어진다.
그 때 매일 찍히는 양의 크기들을 XOR 한 결과를 출력하여라.
[ 풀이 ]
 |
 |
 |
위와 같은 경우를 생각해보자
양은 좌 또는 우로 움직일 것이며 CCTV는 매일 3행, 2열 사이즈의 영역에 대해 사진을 찍는다.
이 때, 3일동안 표시된 박스 내의 가장 큰 값들을 XOR 해야한다.
날이 바뀔 때마다 한 열이 지워지고 새로운 열이 들어오는 것을 볼 수 있다.
그렇다면 열(column) 마다 최대값을 알 수 있다면 구간의 최대를 구하는데 좀 더 편할것이다.
위의 예시로 설명하자면 우리는 이제 다음 정보만 필요하다
$$ 20 \qquad \qquad 18 \qquad \qquad 11 \qquad \qquad 18 $$
이 때, 각 날의 영역의 최대값은 ( 20 , 18 ) , ( 18 , 11 ) , ( 11 , 18 ) 각각의 최대를 구하면 된다.
슬라이딩 윈도우의 느낌으로 구간 사이즈는 CCTV가 보는 열의 크기만큼 잡고 각 구간에서의 최대를 구하면 되는 것이다.
이는 덱을 이용하여 $ O(n) $ 으로 충분히 가능하다.
물론 좌/우 가 아닌 상/하 로 움직일 때 역시 마찬가지이다.
현재까지 시간복잡도를 생각해보면 $ O(Q \; N \: (or \: M) \; X) $ 인데 이 때 X는 한 행 또는 한 열 내에서의 최대를 구하는 시간이다.
물론 나이브하게 계산을 하면 X는 N (or M) 에 가능하다.
하지만 그렇게 되면 연산이 $ 5^3 * 10^8 $ 으로 TLE가 난다.
여기에 sparse array 를 적용하여 한 행 또는 한 열 내에서의 최대값을 구하는 시간을 로그시간으로 낮출 수 있다.
그렇게 되면 시간복잡도는 $ O( Q \; N \; logN ) $ 이며 충분히 통과 가능하다!
[ 코드 ]
// BOJ 17941 목장 CCTV
// Sparse Array & deque dynamic programming
#include <iostream>
#include <vector>
#include <deque>
#include <algorithm>
using namespace std;
// mxsheep[i][j][f][k]
// i 행 j 열에서부터
// f = 0 -> 가로로 / f = 1 -> 세로로
// 2^k 만큼 동안 최대값 - sparse array 구현을 위함
int mxsheep[500][500][2][10];
int main() {
int n, m; cin >> n >> m;
// 가로/세로 모두 2^0 (1칸) 만큼의 최대값은 각 칸의 값
for (int i = 0; i < n; ++i)
for (int j = 0; j < m; ++j) {
cin >> mxsheep[i][j][0][0];
mxsheep[i][j][1][0] = mxsheep[i][j][0][0];
}
// 행 내에서의 최대값을 계산해놓기 위해 sparse array 계산
// mxsheep[i][j][0][k] = max(mxsheep[i][j][0][k-1] , mxsheep[i][j+2^(k-1)][0][k-1])
for (int i = 0; i < n; ++i) {
int pl = 1;
for (int k = 1; k < 10; ++k) {
for (int j = m - 1; j >= 0; --j) {
if (j + pl >= m) mxsheep[i][j][0][k] = mxsheep[i][j][0][k - 1];
else mxsheep[i][j][0][k] = max(mxsheep[i][j][0][k - 1], mxsheep[i][j + pl][0][k - 1]);
}
pl <<= 1;
}
}
// 열 내에서 최대값을 계산해놓기 위해 sparse array 계산
// mxsheep[i][j][1][k] = max(mxsheep[i][j][1][k-1] , mxsheep[i+2^(k-1)][j][1][k-1])
for (int j = 0; j < m; ++j) {
int pl = 1;
for (int k = 1; k < 10; ++k) {
for (int i = n - 1; i >= 0; --i) {
if (i + pl >= n) mxsheep[i][j][1][k] = mxsheep[i][j][1][k - 1];
else mxsheep[i][j][1][k] = max(mxsheep[i][j][1][k - 1], mxsheep[i + pl][j][1][k - 1]);
}
pl <<= 1;
}
}
int q; cin >> q;
while (q--) {
// lur - 좌상단 행 번호 / luc - 좌상단 열 번호
// rdr - 우하단 행 번호 / rdc - 우하단 열 번호
// r - CCTV가 보는 행 사이즈 / c - CCTV가 보는 열 사이즈
// k - 사진을 찍는 날의 수 - 양이 이동하는 방향으로 K-1 만큼 영역이 확장될 예정
// d - 양의 이동방향 1, 2, 3, 4 순서대로 상, 하, 좌, 우
int lur, luc, rdr, rdc, r, c, k, d;
cin >> lur >> luc >> r >> c >> k >> d;
lur--; luc--;
rdr = lur + r - 1, rdc = luc + c - 1;
if (d == 1) rdr += k - 1;
else if (d == 2) lur -= k - 1;
else if (d == 3) rdc += k - 1;
else if (d == 4) luc -= k - 1;
int ans = 0, sz = 0;
vector<int> tmp;
// 양이 상/하 로 움직이는 경우
// 각 행 내부의 최대값을 구하는 sparse array를 이용할 예정이므로 각 행의 최대값을 저장
if (d < 3) {
sz = r;
for (int i = lur; i <= rdr; ++i) {
int len = rdc - luc + 1, seg = 512, res = 0, st = luc;
// sparse array 에서 최대값 쿼리 연산
for (int k = 9; k >= 0; --k) {
if (len < seg);
else {
res = max(res, mxsheep[i][st][0][k]);
st += seg;
len -= seg;
}
seg >>= 1;
}
tmp.push_back(res);
}
}
// 양이 좌/우 로 움직이는 경우
// 각 열 내부의 최대값을 구하는 sparse array를 이용할 예정이므로 각 열의 최대값을 저장
else {
sz = c;
for (int j = luc; j <= rdc; ++j) {
int len = rdr - lur + 1, seg = 512, res = 0, st = lur;
// sparse array 에서 최대값 쿼리 연산
for (int k = 9; k >= 0; --k) {
if (len < seg);
else {
res = max(res, mxsheep[st][j][1][k]);
st += seg;
len -= seg;
}
seg >>= 1;
}
tmp.push_back(res);
}
}
// deque dp 를 이용하여 sliding window 알고리즘을 수행
// 덱은 내림차순으로 저장되어 있고 각 구역의 최대값이 덱의 맨 앞에 위치하게 됨
deque<int> mx;
for (int i = 0; i < tmp.size(); ++i) {
if (mx.size() && mx.front() <= i - sz)
mx.pop_front();
while (mx.size() && tmp[mx.back()] <= tmp[i])
mx.pop_back();
mx.push_back(i);
if (i >= sz -1 )
ans ^= tmp[mx.front()];
}
cout << ans << '\n';
}
}
E. 디저트
[ 문제 설명 ]
창호는 N일 동안 매일 점심동안 디저트를 먹는다.
디저트는 M개 종류가 있고, 하루에는 한 가지 디저트만 먹을 수 있다.
$ ( \; 1 \leq N \leq 100,000 \;\; , \;\; 1 \leq M \leq 10 \; ) $
같은 디저트라도 매일 느끼는 맛이 다르므로 느끼는 만족감도 매일 다르다.
하지만, 전날과 같은 디저트를 먹으면 만족감은 절반으로 감소한다.
이 때, N일 동안 얻는 만족감의 최대값을 구하여라.
[ 풀이 ]
전형적인 최대값을 구하는 DP 문제이다.
점화식은 다음처럼 구하면 된다.
$ dp[i][j] $ = i 일에 j 디저트를 먹어서 얻는 만족감 중, 최대 만족감
$$ dp[i][j] = max \{ \begin{matrix} dp[i-1][k] \; + \; day[i][j] \;\; , \;\; where \; 1 \leq k \leq M \; , k \; \neq \; j \\ dp[i-1][j] \; + \; \frac{day[i][j]}{2} \;\; , \;\; where \; k = j \quad\qquad\qquad \end{matrix} \} $$
시간 복잡도는 $ O(nm^2) $
[ 코드 ]
// BOJ 17953 디저트
// dynamic programming
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
// man[i][j] 1 <= i <= m , 1 <= j <= n , j일에 i디저트를 먹을 때, 만족도
// dp[i][j] 1 <= i <= m , 1 <= j <= n , j일에 i디저트를 먹을 때, 최대 만족도
vector<int> man[10], dp[10];
int main() {
int n, m; cin >> n >> m;
for (int i = 0; i < m; ++i) {
man[i] = dp[i] = vector<int>(n + 1);
for (int j = 1; j <= n; ++j)
cin >> man[i][j];
dp[i][1] = man[i][1];
}
for (int j = 2; j <= n; ++j)
for (int i = 0; i < m; ++i)
for (int k = 0; k < m; ++k)
if (i == k) dp[i][j] = max(dp[i][j], dp[i][j - 1] + man[i][j] / 2);
else dp[i][j] = max(dp[i][j], dp[k][j - 1] + man[i][j]);
int ans = 0;
for (int i = 0; i < m; ++i)
ans = max(ans, dp[i][n]);
cout << ans;
}
F. 알고리즘 공부
[ 문제 설명 ]
희정이는 N개의 알고리즘 중, 최소한 M개의 알고리즘을 공부하려 한다.
$ ( \; 1 \leq M \leq N \leq 100,000 \; ) $
각 알고리즘은 배우기 위해서 $ K_i $ 의 공부량이 필요하다
$ ( \; 1 \leq i \leq N \;\; , \;\; 1 \leq K_i \leq 10^8 \; ) $
알고리즘 사이에는 연관성이 있어서 A 알고리즘을 해결하면 B 알고리즘을 해결하는데 필요한 공부량이 어느정도 줄어든다.
공부량은 누적이며 소모되지 않기 때문에 5의 공부량과 3의 공부량이 필요한 알고리즘이 있다면 모두 공부하기 위해선 총 5의 공부양이 필요하다.
최소 M개의 알고리즘을 공부하기 위한 최소 공부량을 구하여라
[ 풀이 ]
공부량은 누적이므로 공부한 알고리즘들 중, 가장 높은 공부량을 필요로 하는 알고리즘의 공부량이 정답이다.
그렇기 때문에 공부량이 작은 알고리즘을 먼저 배우도록 하자.
하지만 알고리즘의 연관성 때문에 A알고리즘을 배웠다면
A알고리즘을 통해서 공부량이 줄어드는 알고리즘들의 공부량을 줄여줘야 한다.
즉, dijkstra 느낌을 적용해서 어떤 알고리즘의 공부량이 줄어든다면 pq에 집어넣으면서 공부량이 작은 알고리즘을 계속 선택해가자
[ 코드 ]
// BOJ 17942 알고리즘 공부
// dijkstra
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
using pii = pair<int, int>;
int main() {
int n, m; cin >> n >> m;
vector<int> gong(n + 1);
for (int i = 1; i <= n; ++i)
cin >> gong[i];
int q; cin >> q;
vector<vector<pii>> adj(n + 1);
while (q--) {
int u, v, w; cin >> u >> v >> w;
adj[u].push_back({ v, w });
}
priority_queue<pii, vector<pii>, greater<pii>> pq;
// 공부했는지 여부를 파악하기 위한 visit 배열
vector<int> vis(n + 1);
for (int i = 1; i <= n; ++i)
pq.push(pii(gong[i], i));
int ans = -1, c = 0;
while (!pq.empty() && c < m) {
auto cc = pq.top(); pq.pop();
// 이미 공부한 과목
if (vis[cc.second]) continue;
c++;
vis[cc.second] = 1;
ans = max(ans, cc.first);
for (auto nn : adj[cc.second]) {
int nxt = nn.first;
// 연관성있는 과목을 이미 공부했다면 pass
if (vis[nxt]) continue;
// 공부량 감소
if (gong[nxt] >= nn.second) gong[nxt] -= nn.second;
else gong[nxt] = 0;
pq.push(pii(gong[nxt], nxt));
}
}
cout << ans;
}
G. 흩날리는 시험지 속에서 내 평점이 느껴진거야
[ 문제 설명 ]
현수의 시험지가 N장이 있었는데 모두 날아가버렸다.
$ ( \; 1 \;leq K \leq N \leq 10^5 \; )
마음씨 좋은 조교는 많은 점수는 줄 수 없기 때문에 N장의 시험지를 순서를 유지한 채로 K개의 그룹으로 나누어
각 그룹에서 맞은 문제 개수의 합을 구해, 그 중 최솟값으로 점수를 주기로 했다.
현수가 받을 수 있는 최대 점수를 구하여라
각 시험지의 맞은 문제는 0개 ~ 20개 이다.
[ 풀이 ]
현수가 만약 X 점을 받을 수 있다면 모든 그룹은 X점 이상이다.
그리고 N개의 시험지를 X점 이상이 되도록 그룹을 나누었을 때, 최소 K개의 그룹이 나오게 된다.
위에서 설명한 조건을 이용해서 이분 탐색을 하면 된다.
최소 점수는 0, 최대 점수는 N * 20 으로 잡고 위에서 설명한 조건을 만족하면 low를 mid로 올리고 그 반대라면 high를 mid로 줄이면 된다.
[ 코드 ]
// BOJ 17951 흩날리는 시험지 속에서 내 평점이 느껴진거야
// Binary search
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
int n, k; cin >> n >> k;
vector<int> seq(n);
for (int i = 0; i < n; ++i) cin >> seq[i];
int l = 0, r = *max_element(seq.begin(), seq.end()) * n + 1;
while (l + 1 < r) {
int mid = (l + r) / 2;
// c - 그룹 개수, tmp - 그룹의 점수를 쌓아갈 변수
int c = 0, tmp = 0;
for (int i = 0; i < n; ++i) {
tmp += seq[i];
// 그룹의 점수가 mid 이상이 되면 바로 그룹을 자르기
if (tmp >= mid) {
c++;
tmp = 0;
}
}
if (c >= k) l = mid;
else r = mid;
}
cout << l;
}
H. 투튜브
[ 문제 설명 ]
민서는 투튜브의 유명 BJ이며 열혈팬 성주로부터 2개의 튜브에 사과가 N개씩 들어간 선물을 받았다.
$ ( \; 1 \leq N \leq 10,000 \; ) $
각 사과의 크기는 1부터 2N 까지 중복되어있지 않다.
민서는 하루에 하나씩 사과를 꺼내는데 두 튜브의 양쪽 끝에 나와있는 사과 중 가장 작은 크기의 사과를 꺼낼 수 있다.
그런데 사과는 부패를 하는데 이 때, T일에 x 크기의 사과는 T x 만큼 부패를 하게 된다.
총 부패도가 최소가 되도록 사과의 배치도와 총 부패도를 출력하여라
[ 풀이 ]
높은 크기의 사과는 최대한 빨리 먹어야 총 부패도를 줄일 수 있다.
그럼 가장 큰 사과 4개를 튜브의 양쪽 끝에 배치해보자
$$ 2N-3 \;\; ... \;\; ... \;\; ... \;\; ... \;\; 2N-2 \\ 2N-1 \;\; ... \;\; ... \;\; ... \;\; ... \;\; 2N $$
이 때, 가장 작은 크기를 선택하기 때문에 2N-3 을 선택한다.
2N-3 을 선택하면서 새로운 사과가 등장하는데 이 사과는 나머지 세 사과보다 무조건 작으므로 다음에 선택된다.
그렇기 때문에 2N-3의 오른쪽으로 2N-4부터 1씩 작아지도록 배치한다.
$$ 2N-3 \;\; 2N-4 \;\; 2N-5 \;\; ... \;\; ... \;\; N-1 \;\; 2N-2 \\ 2N-1 \;\; ... \;\; ... \;\; ... \;\; ... \;\; 2N $$
다음과 같이 배치하면 2N-3 부터 N-1까지 꺼낸 다음, 2N-2 , 2N-1 을 순서대로 꺼낸다.
그 이후에 남은 사과는 N-2 부터 1까지와 2N이 있다.
그렇기 때문에 2N-1을 꺼냄으로써 보이는 사과는 N-2여야 최선이다.
이후는 1까지 순서대로 배치하면된다
$$ 2N-3 \;\; 2N-4 \;\; 2N-5 \;\; ... \;\; ... \;\; N-1 \;\; 2N-2 \\ 2N-1 \;\;\; N-2 \;\;\; N-3 \;\;\; ... \;\; ... \;\;\;\;\; 1 \;\;\;\;\; 2N $$
[ 코드 ]
// BOJ 17954 투튜브
// Greedy
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
using ll = long long;
int main() {
int n; cin >> n;
if (n == 1) {
cout << 2 << '\n' << 1 << '\n' << 2;
return 0;
}
vector<int> seq;
for (int i = 2 * n - 3; i >= n - 1; --i) seq.push_back(i);
seq.push_back(2 * n - 2);
seq.push_back(2 * n - 1);
for (int i = n - 2; i > 0; --i) seq.push_back(i);
seq.push_back(2 * n);
ll sum = 1LL * n * (2 * n + 1);
ll ans = 0;
for (int i = 0; i < 2 * n; ++i) {
sum -= seq[i];
ans += (i + 1) * sum;
}
cout << ans << '\n';
cout << 2 * n << ' ';
for (int i = 1; i <= n - 2; i++) cout << i << ' ';
cout << 2 * n - 1 << '\n';
cout << 2 * n - 2 << ' ';
for (int i = n - 1; i <= 2 * n - 3; ++i) cout << i << ' ';
}
I. Gazzzua
[ 문제 설명 ]
정명이는 타임머신을 개발하여 주홍코인의 가격 변동 차트를 이용해 수익을 벌려고 한다.
주홍 코인의 구매는 매 분마다 1개만 가능하고
주홍 코인의 판매는 몇 개들 할 수 있다.
또한, 모든 거래는 수수료가 발생하지 않는다.
[ 풀이 ]
i 분에 산 코인이 이득을 보기 위해서는 i+1 ~ N분의 시간 중, 최대 가격일 때 팔면 된다.
물론 i분의 가격보다 비싸야 한다.
for 문을 한바퀴 돌려서 각 i 분 이후에 최대 가격을 저장해놓고 그 최대 가격과 i 분의 가격을 뺀 값들을 모두 더하면 된다.
[ 코드 ]
// BOJ 17939 Gazzzua
// Greedy
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
int n; cin >> n;
vector<int> coin(n + 1);
for (int i = 1; i <= n; ++i) cin >> coin[i];
// mx - i분 이후의 최대 가격
// 초기화는 현재 가격이 최대
vector<int> mx(n + 1);
for (int i = 1; i <= n; ++i) mx[i] = coin[i];
int m = coin[n];
// 뒤에서부터 최대 가격을 쌓아오면서 mx 배열에 값을 갱신
for (int i = n - 1; i > 0; --i) {
m = max(coin[i], m);
mx[i] = m;
}
int ans = 0;
// i 분에 구매한 코인을 통해 벌 수 있는 이익 = mx[i] - coin[i]
for (int i = 0; i < n; ++i)
ans += mx[i] - coin[i];
cout << ans;
}
J. 지하철
[ 문제 설명 ]
대학원생 형욱이는 연구실에 출근할 때, 지하철을 이용한다.
지하철은 A, B 두 회사에서 운영하며 두 회사는 경쟁사이기 때문에 다른 회사가 운영하는 지하철역으로 이동할 때, 환승횟수가 늘어난다.
형욱이는 가난한 대학원생이므로 최적의 출근 경로를 찾고 싶다.
최적의 출근 경로는, 환승 횟수를 최소로 하며 소요시간이 짧은 경로이다.
지하철역은 N개가 있으며 출발지는 항상 0 이며 도착지의 번호는 M이다.
$ ( \; 2 \leq N \leq 1000 \;\; , \;\; 0 < M < 1000 \; ) $
[ 풀이 ]
단일 출발 - 단일 도착 최단 경로 를 찾는 문제이다.
이 때 최단 경로의 의미는 환승 횟수가 적을 수록, 소요시간이 적을 수록 이다.
이 조건에 맞게 다익스트라를 잘 돌려주면 된다.
[ 코드 ]
// BOJ 17940 지하철
// dijkstra
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
const int inf = 1e9;
struct node {
int count, time, u;
};
// 횟수가 적을수록, 같다면 시간이 적을수록 우선순위를 주기위한 compare 함수
bool operator < (node a, node b) {
if (a.count == b.count) return a.time > b.time;
return a.count < b.count;
}
int main() {
int n, m; cin >> n >> m;
vector<int> ab(n);
for (int i = 0; i < n; ++i)
cin >> ab[i];
vector<vector<node>> adj(n);
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
int x; cin >> x;
if (!x) continue;
// 연결된 지하철이 같은 회사면 count는 0 증가
if (ab[i] == ab[j]) adj[i].push_back({ 0, x, j });
// 다른 회사면 count 1 증가
else adj[i].push_back({ 1, x, j });
}
}
vector<int> count(n, inf), time(n, inf);
count[0] = 0; time[0] = 0;
priority_queue<node> pq;
pq.push({ 0, 0, 0 });
while (!pq.empty()) {
auto tp = pq.top(); pq.pop();
int cnt = tp.count, tm = tp.time, cur = tp.u;
for (auto next : adj[cur]) {
int ncnt = cnt + next.count, ntm = tm + next.time, nxt = next.u;
// 횟수가 더 적다면
if (count[nxt] > ncnt) {
count[nxt] = ncnt;
time[nxt] = ntm;
pq.push({ ncnt, ntm, nxt });
}
// 횟수가 같지만 시간이 더 덜걸린다면
else if (count[nxt] == ncnt && time[nxt] > ntm) {
time[nxt] = ntm;
pq.push({ ncnt, ntm, nxt });
}
}
}
cout << count[m] << ' ' << time[m];
}
K. 도미노 예측
[ 문제 설명 ]
숫자 도미노의 도미노에는 각각 어떤 수가 쓰여있고 N개의 도미노가 일열로 연결되어 있다.
i번 도미노와 i+1번 도미노의 XOR 한 값들을 알고있다고 할 때, 다음 2가지 질문에 답하도록 하여라.
$ ( \; 3 \leq N \leq 2 * 10^5 \;\; , \;\; 1 \leq i \leq N-1 \; ) $
1) x번째 도미노의 수와 y번째 도미노의 수를 XOR 한 값을 구하여라
2) s번째 도미노의 수가 d일 때, y번째 도미노의 수를 답하여라
질문은 총 Q번 주어진다.
$ ( \; 1 \leq Q \leq 10^5 \; ) $
[ 풀이 ]
각 도미노에 작성된 수를 $ X_i $ 라고 하자.
그렇다면 초기에 알고 있는 XOR 값들의 리스트는 다음과 같다.
$$ X_1 \oplus X_2 \; , \; X_2 \oplus X_3 \; , \; X_3 \oplus X_4 \; , \; ... \; , \; X_{n-1} \oplus X_n $$
XOR 연산에 대하여 다음이 만족된다.
$$ 0 \; \oplus \; X \; = \; X \\ X \; \oplus \; X \; = \; 0 $$
1) x번째 수와 y번째 수를 XOR 한 값을 구하기 위해서는 다음과 같이 구할 수 있다.
$$ ( \; X_x \oplus X_{x+1} \; ) \oplus ( \; X_{x+1} \oplus X_{x+2} \; ) \oplus ... \oplus ( \; X_{y-1} \oplus X_y \; ) $$
2) x번째 수가 d일 때 y번째 수를 구하기 위해서는 1) 식에 살짝 추가하면 된다.
$ X_x $ 와 $ X_y $ 의 XOR 결과 값을 알고 있기 때문에 해당 값에 $ X_x $ 를 XOR 시키면 $ X_y $ 값을 구할 수 있다.
$$ X_y = X_x \oplus ( \; X_x \oplus X_y \; ) $$
참고로 내 코드는 seg tree를 이용해서 구간 xor 값을 관리 했지만 update가 없기 때문에 prefix sum 을 통해서 해도 상관없다.
[ 코드 ]
// BOJ 17943 도미노 예측
// Segment tree (Prefix Sum 으로도 가능)
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
using ll = long long;
struct Seg {
int n, half;
vector<ll> item;
Seg(int n_) : n(n_) {
for (half = 1; half < n; half <<= 1);
item = vector<ll>(half * 2);
}
void init(vector<ll>& v) {
for (int i = 0; i < n; ++i) item[i + half] = v[i];
for (int i = half - 1; i; --i) item[i] = item[i * 2] ^ item[i * 2 + 1];
}
ll xorq(int l, int r) {
ll ret = 0;
l += half; r += half;
while (l <= r) {
if (l % 2) ret ^= item[l++];
if (!(r % 2)) ret ^= item[r--];
l >>= 1; r >>= 1;
}
return ret;
}
};
int main() {
int n, q; cin >> n >> q;
vector<ll> ij(n);
for (int i = 0; i < n - 1; ++i)
cin >> ij[i];
Seg seg(n - 1);
seg.init(ij);
while (q--) {
ll c, x, y, d;
cin >> c >> x >> y;
x--; y--;
// 1번 질문
if (!c) cout << seg.xorq(x, y - 1) << '\n';
// 2번 질문
else {
cin >> d;
ll xx = seg.xorq(x, y - 1);
cout << (d ^ xx) << '\n';
}
}
}