#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을 보면서 공부좀 해 보아야 겠다.