Hadi Partovi가 이끄는 비영리 단체로, 미국의 모든 학생들이 컴퓨터 과학을 배우도록 장려하기 위해 만들어진 사이트이다. 한국어도 어느정도 지원하고, 엔트리와 마찬가지로 블럭 코딩으로 게임과 같은 방식으로 프로그래밍을 재미있게 배울 수 있는 환경을 웹 상에서 제공한다.
볼륨을 a에서 b로 변경해야 하는데, 볼륨은 음수가 불가능하고 버튼 한번을 눌러서 +- 1,2,5 중 하나의 액션을 할 수 있다.
총 6가지 액션이 가능한 셈이다.
버튼을 최소 횟수를 눌러서 볼륨을 a에서 b로 변경할 때, 최소 누르는 횟수를 알아내는 문제이다.
뭔가 bfs로 탐색을 해야 정확할 것 같은 느낌인데, 케이스를 나눠서 보면 그리디하게 풀린다.
만약 a와 b의 절댓값 차이가 5이하인 경우들을 체크해보자.
차이가 5인 경우 = +5를 한번 누름
차이가 4인 경우 = +2를 두번 누름 = 혹은 +5를 한번, -1를 한번 누름
차이가 3인 경우 = +2를 한번 +1를 한번 누름 = +5를 한번, -2를 한번 누름
차이가 2인 경우 = +2를 한번 누름 < +5를 한번, -2를 한번, -1를 한번 해서 총 3번 누름
차이가 1인 경우 = +1를 한번 누름 < +5를 한번 -2를 두번 해서 총 3번 누름
차이가 5초과인 경우는 5를 누르는 것이 최소로 줄이는 것이 자명한 상태이다.
차이가 5이하인 경우도, +5와 -를 조합하는 경우와 +만으로 누르는 경우를 비교했을 때, +만으로 조합하는 경우가 횟수가 작거나 같다.
따라서 차이값에 대하여 큰 단위부터 누르면 된다.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define endl '\n'
void solve() {
int a, b;
cin >> a >> b;
int diff = abs(a - b);
int ans = 0;
ans += diff / 5;
diff %= 5;
ans += diff / 2;
diff %= 2;
ans += diff;
cout << ans << endl;
}
int main() {
int tc;
cin >> tc;
while (tc--) solve();
}
냉장고가 private 해 지기 위해서는, 서로다른 2개 이상의 냉장고와 연결된 체인이 있어야 한다.
이 조건은 모든 냉장고에 다 적용되어야 하므로, 최소 냉장고 개수와 동일한 수의 체인이 있어야 조건이 맞게 만들 수 있다. (체인 하나 당 2개의 냉장고를 연결하므로)
그리고 cost는 냉장고별 고유값을 더한 값이므로, 어차피 모든 냉장고는 고유값 * 2만큼은 코스트를 써야 한다는 점에
그냥 원형으로 체인을 덮은 뒤, 남는 체인들은 a값이 가장 낮은 냉장고에 걸어버리는 식으로 풀이를 했다.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define endl '\n'
typedef pair<int, int> pii;
pii a[2005];
void solve() {
int n, m;
cin >> n >> m;
int total = 0;
for (int i = 0; i < n; i++) {
a[i].second = i + 1;
cin >> a[i].first;
total += a[i].first;
}
total *= 2;
sort(a, a + n);
if (m < n || n <= 2) {
//impossible
cout << -1 << endl;
return;
}
int rest = m - n;
total += rest * (a[0].first + a[1].first);
cout << total << endl;
for (int i = 1; i < n; i++) {
cout << i << ' ' << i + 1 << endl;
}
cout << n << ' ' << 1 << endl;
for (int i = 0; i < rest; i++) {
cout << a[0].second << ' ' << a[1].second << endl;
}
}
int main() {
int tc;
cin >> tc;
while (tc--) {
solve();
}
}
Permutation 원본에서, 원래 위치에서 3개씩 끊어서 자른 뒤 3개짜리 묶음의 순서와, 묶음 내 순서를 마구잡이로 섞은 것을 준다.
이를 통해 원본을 알아내야 하는데,
인접한 묶음들은 2개의 숫자가 동일하다는 것을 알 수 있다.
그리고 처음과 끝에 등장하는 숫자 하나는 단 한번만 등장한다는 특징이 있으므로, 이를 이용해서 하나하나 연결시켜서
찾아나가면 된다.
구현이 좀 귀찮았던 문제이다.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define endl '\n'
int arr[100005][4];
vector<int> pos[100005];
vector<int> tail, subtail;
int find_val(int a, int b, int no) {
for (int i = 0; i < pos[a].size(); i++) {
for (int j = 0; j < pos[b].size(); j++) {
if (pos[a][i] == pos[b][j]) {
int idx = pos[a][i];
int candid = arr[idx][3] - a - b;
if (candid != no) {
return candid;
}
}
}
}
assert(false);
return -1;
}
int find_pos(int a, int b) {
for (int i = 0; i < pos[a].size(); i++) {
for (int j = 0; j < pos[b].size(); j++) {
if (pos[a][i] == pos[b][j]) {
return pos[a][i];
}
}
}
assert(false);
return -1;
}
int main() {
int n;
cin >> n;
for (int i = 1; i <= n - 2; i++) {
int a, b, c;
cin >> a >> b >> c;
arr[i][0] = a;
arr[i][1] = b;
arr[i][2] = c;
arr[i][3] = a + b + c; //summation
pos[a].push_back(i);
pos[b].push_back(i);
pos[c].push_back(i);
}
for (int i = 1; i <= n; i++) {
if (pos[i].size() == 1) tail.push_back(i);
else if (pos[i].size() == 2) subtail.push_back(i);
}
vector<int> ans;
int no = tail[0];
ans.push_back(no);
vector<int> rest;
for (int i = 0; i < 3; i++) {
int val = arr[pos[no][0]][i];
if (val == tail[0]) continue;
rest.push_back(val);
}
int prev;
if (pos[rest[0]].size() == 2) {
ans.push_back(rest[0]);
ans.push_back(rest[1]);
prev = rest[0];
}
else {
ans.push_back(rest[1]);
ans.push_back(rest[0]);
prev = rest[1];
}
while(ans.size() < n) {
//int position = find_pos(prev, ans.back());
//int next = arr[position][3] - prev - ans.back();
int next = find_val(prev, ans.back(), no);
no = prev;
prev = ans.back();
ans.push_back(next);
}
for (auto v : ans) {
cout << v << ' ';
}
cout << endl;
return 0;
}
이것도 구현형 문제이다. 닭들이 Rice가 포함된 셀을 가장 비슷하게 가져가도록 만들면 된다.
전체 Rice 수를 R, 닭의 수를 K라고 할 때 //(floor(R/K)//)를 각자 주고, //(R - floor(R/K)*K//)만큼의 닭에게는 +1만큼 더 지급한다고 치면 된다.
그리고 땅 분할은 맨 위 row부터 지그재그로 가로로 훑고 내려오는 식으로 할당하면 된다.
첫줄을 왼쪽에서 오른쪽으로 훑고, 두번째 줄은 오른쪽에서 왼쪽으로 훑고, 그담에 다시 왼쪽에서 오른쪽
이런식으로 훑으면서 내려가면 인접한 땅을 할당하되 중복 할당 되지 않도록 할 수 있다.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define endl '\n'
vector<char> chick;
vector<int> needs;
string field[105];
int row_rices[105];
void solve() {
int total_rices = 0;
int r, c, k;
cin >> r >> c >> k;
memset(row_rices, 0, sizeof(row_rices));
needs.clear();
for (int i = 0; i < r; i++) {
cin >> field[i];
for (char c : field[i]) {
if (c == 'R') row_rices[i]++;
}
total_rices += row_rices[i];
}
int each = total_rices / k;
int rest = total_rices - each * k;
for (int i = 0; i < rest; i++) {
needs.push_back(each + 1);
}
for (int i = rest; i < k; i++) {
needs.push_back(each);
}
int x, y, dir;
x = y = 0;
dir = +1;
for (int i = 0; i < k; i++) {
int need = needs[i];
char ch = chick[i];
int got = 0;
while (got < need || i+1 == k) {
if (y == -1) {
dir = +1;
y = 0;
x++;
}
else if (y == c) {
dir = -1;
y = c - 1;
x++;
}
if (x == r) break;
if (field[x][y] == 'R') {
got++;
}
field[x][y] = ch;
y += dir;
}
}
for (int i = 0; i < r; i++) {
cout << field[i] << endl;
}
return;
}
int main() {
for (char c = '0'; c <= '9'; c++) chick.push_back(c);
for (char c = 'a'; c <= 'z'; c++) chick.push_back(c);
for (char c = 'A'; c <= 'Z'; c++) chick.push_back(c);
int tc;
cin >> tc;
while (tc--) solve();
return 0;
}
E번부터는 풀지를 못했고 이해도 좀 덜 했는데, Editorial을 보면서 공부좀 해 보아야 겠다.
사실 완전히 잘못 알고 있던 것은 아니고, 에라토스테네스의 채에서 어느정도 스킵하고 지나가야 하는 부분도, 잘 못 믿고 더블체크를 하는 과정이 항상 있었다.
이 과정에서 조금 비효율적이었지만, 크게 상관은 없는 그런.. 상황이었다.
에라토스테네스의 채는 알려진 소수를 하나 알게 되면, 그 소수의 배수들을 모조리 없애버리는 소거식으로 한 뒤, 남은 수들은 소수라고 보는 방식이다.
N=500만, 인 상황에서 N보다 작은 모든 소수를 구해야 하는 상황이다.
기존에 내가 잘못 알고 있던 부분은 2부터 시작해서 채에 걸러지지 않은 녀석들이 소수가 맞는지 2부터 sqrt(n)까지의 수로 다시 나누어서 확인하고 있었는데, 이 부분 때문에 TLE가 많이 났다.
2부터 이미 채에 걸러지지 않았다면, 그냥 소수가 맞다고 보면 된다.
왜 그런가 하면..
//(N//)이하의 소수를 다 구한다고 하면, //(\sqrt{N}//)이하의 소수의 배수들을 다 소거했을 때, //([\sqrt{N}, N]//) 범위에 있는 걸러지지 않은 모든 수는 소수가 맞다.
왜 그런가 하면 귀류법으로 증명이 가능하다.
만약 //([\sqrt{N}, N]//)사이에 걸러지지 않았지만, 소수가 아닌 합성수가 존재한다고 가정해 보자.
이 수를 K라고 하겠다.
이 수는 합성수이므로 //(K=p*q//)로 인수분해가 가능할 것이다. //(p, q//)는 소수 일 수도 있고 아닐 수도 있다.
어쨋든 이 사실로 인하여, //(min(p, q) <= \sqrt{N}//)라는 사실이 성립한다. 그렇다는 것은 //(p//)나 //(q//)중 하나의 수는
소수의 배수들을 소거할 때 무조건 한번은 출연을 했다는 것이다.
//(p//)나 //(q//)중 작은 수가 합성수라면, 이미 그 보다 작은 소수의 배수로서 등장을 했을 것이고, 소수라고 하더라도
모든 소수가 다 걸러졌기 때문에 걸려졌을 것이다.
그러므로, 해당 범위 //([\sqrt{N}, N]//)에는 합성수가 남아있을 수 없다.
뭐 이런 결론이 된다.
" //(\sqrt{N}//)이하의 소수의 배수들을 다 소거했을 때," 이 사실이 참이라면 성립하게 된다.
이런식으로 Inductive step이 성립하게 되었으니, 수학적 귀납법으로도 확장이 가능할 것으로 보인다.
뭐 그래서 맞을 것이다.
맞겟지 아마 증명이?
틀린 부분이 있다면 얼마든지 지적, 조언 등 환영합니다.
그래서 제곱근까지의 소수로만 확장시켜도 그 위도 다 소수가 남아있는게 맞다고 합니다.
그리고 소수를 찾아서 그 배수들을 소거할 때, 만약 소수 //(p//)를 찾았다면 다음 첫 소거 아이템은 //(p^2//)부터 시작해도 된다고 한다.
이미 그 이전 것들은 즉, //(p, p*2, p*3, ... , p*(p-1)//)는 다 소거가 되었다고 볼 수 있다. 오른쪽에 붙는 //([1, p-1]//)에 해당하는 수 들은
소수이면 이미 다 체크되었고, 합성수라면 또 어느 소수의 배수로 다 체크되었기 때문에 다 걸려있다 이말입니다. ㅠ
하 이 부분을 제대로 짚고 공부하지 않아서 이렇게 빵꾸가 나버린 논리 ㅠ
고로 구현한 코드는..
그런점을 이용하면 소수를 쉽게 구할 수 있다.
그리고 채를 bool 배열로만 잡았었는데, int로 잡아서 다음과 같게도 구현이 가능하더라..
int배열에 들어가는 값은, int arr[i]라 하면 i가 갖는 가장 작은 소인수 값이 해당 배열에 들어가게 하면 쉽~게 소인수 분해를 하도록 만들 수 있다더라 ㅠ
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
typedef long long ll;
typedef pair<int, int> pii;
int min_factor[5000005];
void solve(int n) {
while (n > 1) {
printf("%d ", min_factor[n]);
n /= min_factor[n];
}
putchar('\n');
}
int main() {
min_factor[0] = min_factor[1] = -1;
for (int i = 2; i <= 5000000; i++) {
min_factor[i] = i;
}
for (int v = 2; v * v <= 5000000; v++) {
if (min_factor[v] == v) { //v가 소수라면
for (int k = v * v; k <= 5000000; k += v) {
if (min_factor[k] == k)
min_factor[k] = v;
}
}
}
int n;
scanf("%d", &n);
while (n--) {
int v;
scanf("%d", &v);
solve(v);
}
return 0;
}
