#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
typedef long long ll;
typedef pair<int, int> pii;
vector<int> arr;
int need(int width) {
// 색종이 폭이 width일때, 다 덮기 위해 필요한 종이의 수
int prev = -1;
int ret = 0;
for (int pos : arr) {
if (prev == -1) {
//처음 종이를 놓는 경우, [prev, prev+width) 까지 커버 가능
prev = pos;
ret++;
}
else if (prev + width <= pos) {
prev = pos;
ret++;
}
}
return ret;
}
int main() {
int row, col, num_paper, num_hole;
int max_height = 0;
cin >> row >> col >> num_paper >> num_hole;
for (int i = 0; i < num_hole; i++) {
int x, y; //행, 열
cin >> x >> y;
max_height = max(max_height, x);
arr.push_back(y);
}
sort(arr.begin(), arr.end());
int l = max_height;
int r = 1000000; //range = [l, r]
while (l < r) {
int m = (l + r) / 2;
if (need(m) <= num_paper) {
//가능한 경우
r = m;
}
else {
l = m + 1;
}
}
cout << l << endl;
return 0;
}
즉 1 500000 1000001 이렇게 인데, 사실 100만1은 안나오지만, 대충 타일 값 차이가 50만 가까이가
최대값이라고 보면 된다.
따라서 타일간 차이값인 diff값을 모두 다 찾아보면서 순회하려면 diff값이 50만개가 될 것이고
diff값 별 타일 모두를 다 훑어야 하므로 for-loop 도는 횟수는 50만 * 3천 정도 인데
이 값은 15억 정도 되므로, 15초 이상 걸리는 알고리즘 이라고 볼 수있다. 고로 Time Limit Exceed가
자명한 알고리즘이라는 뜻
그러면 이 계산량을 줄여야 하는데, N값이 3000이므로 꽤나 작다.
3000이라면 //(O(N^2)//)알고리즘을 짜도 돌아간다는 뜻.
여기서 잘 모르겠어서 아래의 알고리즘 분류를 "보기"를 눌러서 확인해 보았는데
다이나믹 프로그래밍이라고 힌트를 얻었다.
그러면 N값을 기준으로 메모이제이션 배열을 활용하면 될 것 같은데, N크기에 맞는 2차원 디피까지는 가능할 것 같다.
그렇다면 dp 배열 인덱스에 diff값을 넣을 수는 없다. 메모리 문제도 있고 시간 문제도 있고
그래서 //(dp[3000][3000]//)식으로 잡고, //(dp[i][j]//)라 했을 때, //(i//)가 마지막 인덱스고 //(j//)가 직전 인덱스로 해서
//(arr[i] - arr[j]//)로 diff값을 구할 수 있으니, 이를 활용해 보기로 했다.
dp[i][j] = i번째에서 끝나고, 그 직전에 arr[j]의 값을 갖는 시퀀스 합의 최대값
이라고 정의해보자.
처음 3개짜리만 대상으로 dp배열을 모두 전처리 해 놓은 뒤,
모든 dp배열을 돌면서, arr[j], arr[i]를 통해서 다음에 나올 수 있는 값을 구해서, 그 값이 존재하는 지
확인한 뒤, 존재한다면 그 인덱스를 //(k//)라 하고, //(dp[k][i]//)에 //(dp[i][j] + arr[k]//)를 넣는 식으로 구하면 될 듯하다.
값이 존재하는지는, 값의 범위가 1부터 100만이므로 배열을 잡기 보다는 c++ stl map같은 자료구조를 쓰면 좋을 것 같다.
배열로 잡는다면 값 자체는 3000개라서 sparse한 배열이 될 것이고, 메모리가 터질 수 있으므로
구현 코드
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define endl '\n'
int arr[3005];
map<int, int> mm;
ll dp[3005][3005]; // dp[i][j] => i번째에서 끝나고, 이전이 j인 시퀀스의 최대 누적합
int main() {
ll ans = 0;
int n;
cin >> n;
for (int i = 0; i < n; i++) {
int tmp;
cin >> tmp;
arr[i] = tmp;
mm[tmp] = i;
}
for (int i = 1; i < n; i++) {
int cur = arr[i];
for (int j = 0; j < i; j++) {
int prev = arr[j];
ll next = cur + (cur - prev);
if (mm.find(next) != mm.end()) {
int next_idx = mm[next];
dp[next_idx][i] = cur + prev + next;
ans = max(ans, dp[next_idx][i]);
}
}
}
for (int i = 1; i < n; i++) {
int cur = arr[i];
for (int j = 0; j < i; j++) {
if (dp[i][j]) {
int prev = arr[j];
ll next = cur + cur - prev;
if (mm.find(next) != mm.end()) {
int next_idx = mm[next];
dp[next_idx][i] = dp[i][j] + next;
ans = max(ans, dp[next_idx][i]);
}
}
}
}
cout << ans << endl;
return 0;
}
2008년도 초등부 문제 풀어보다가 1번 문제라서 쉽겠거니 하고 했다가 우수수 하고 틀려버렸다 ㅡㅡ
문제 내용은 크게 어려운 것은 없다.
규칙에 맞게 절사평균과 보정 평균을 구해주면 되는데, 배열로 받은 뒤 소팅해서
앞에 k개 만큼을 날리던지, 근처 값으로 변경해주던지 하면 된다.
하 그놈의 Floating Point 정확도 문제
Floating Point precision 문제때문에 하....
일단 입력값 중 점수는 0 ~ 10범위의 실수에 소숫점 한자리까지 나오는 floating point이고
전채 개수가 10만개 까지 나올 수 있다.
10만개라는 이유 때문에 precision 문제가 발생할 수 있다.
컴퓨터에서 사용하는 부동소수점 방식은 작은 에러값이 발생할 수 있다.
따라서 이게 누적되면 정확하지 않은 값이 나올 수 있는데
따라서 정수로 환원해서 풀어야 한다.
결과값은 소수점 2자리까지 출력해야하고, 이로 인해서 100을 곱하면 되겠지만, 소수점 셋째자리에서
반올림을 해야 하므로 1000을 곱해서 소수점 셋째자리까지 일단 표현 가능하게 정수로 받았다.
그리고 마지막에 5를 더해서 반올림을 구현했다.
출력할때는 1000을 나눈 정수 부분과 1000로 모듈러 연산을 한 소수부분(fraction)을 따로 출력해주었다.
5가 정답일 때 5.00라고 출력해야 하므로 포맷 스트링에 0 extension도 해 주어야 한다.
%02d와 같이 하면 너비 2만큼 0을 꽉채워서 출력해준다.
구현 코드
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define endl '\n'
int main() {
int n, k;
vector<ll> arr;
cin >> n >> k;
arr.resize(n);
for (int i = 0; i < n; i++) {
double tmp;
cin >> tmp;
arr[i] = (ll)(tmp * 1000);
}
sort(arr.begin(), arr.end());
ll s = 0;
for (int i = k; i + k < arr.size(); i++) {
s += arr[i];
}
ll ans = s / (arr.size() - k - k) + 5;
printf("%lld.%02lld\n", ans / 1000, ans % 1000 / 10);
s = 0;
s += k * arr[k];
for (int i = k; i + k < arr.size(); i++) {
s += arr[i];
}
s += k * arr[arr.size() - 1 - k];
ans = s / arr.size() + 5;
printf("%lld.%02lld\n", ans / 1000, ans % 1000 / 10);
}
블로그들 특성상, 어느정도 틀린 내용이 있을 수 있으나 전체적으로 틀을 잡는데는 도움이 많이 될 것이다.
컴퓨터 공학 입문
영어권에서는 컴퓨터 과학(Computer science)이라는 단어로도 자주 쓰이는데 엄밀하게는 컴퓨터 공학과 과학은 다르긴 하지만, 여기서는 그러한 단어의 엄밀한 뜻 보다는 "프로그래밍을 지속적으로 하기 위한 기초체력과 같은 지식"라고 이해하시면 편하다. 우선 이러한 지식을 알려줄 수 있는 강의 사이트들을 추천해보도록 하겠다.
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;
}
