b형 코테 보려고 푼다. 음 막상 풀어보니까 쉽지 않다. iostream만 쓴다는건 더 정확하게 설계해야 한다. 난 중간에 하다가 뒤집어서 시간이 오래걸린다.!!!
9088. 다이아몬드
음 배열이 주어지면 서로 차이가 K이하인 것들을 모았을때 최대가 되도록 하는 갯수를 구해야 한다.
다이아몬드 갯수는 1000개 이하라 n^2도 가능하다.
이중 for문으로 각 다이아에 대해 다른 다이아들이 K이하인지 확인하면 될듯? -> 안된다. 이런식으로 넣으면 확인하는 대상 두개 말고 넣어진 애들끼리 K 이상일 수 도 있다.
아니면 오름 차순으로 정렬하고 앞에서 부터 차례로 K 이하인 놈들끼리만 넣어보는거다.
근데 이때 틀리고 알게된건데 가장 작은 놈이랑 새로 넣으려는 놈의 K만 비교하면 된다. 즉 그냥 우선순위 queue 문제일듯?
시간이 45ms이다. 이걸 10ms로 줄여보자.
#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
int N, K;
vector<int> arr;
int main(int argc, char** argv)
{
int test_case;
int T;
//freopen("input.txt", "r", stdin);
cin >> T;
for (test_case = 1; test_case <= T; ++test_case)
{
cin >> N >> K;
arr.clear();
for (int i = 0; i < N; i++) {
int tmp;
cin >> tmp;
arr.push_back(tmp);
}
int maxv = 0;
sort(arr.begin(), arr.end());
for (int k = 0; k < N; k++) {
vector<int> vec;
vec.push_back(arr[k]);
for (int j = k; j < N-1; j++) {
if (arr[j + 1] - arr[j] <= K && arr[j+1] - arr[k] <= K) {
vec.push_back(arr[j + 1]);
}
}
if (maxv < vec.size()) {
maxv = vec.size();
}
vec.clear();
}
cout <<"#"<< test_case<<" "<< maxv<<"\n";
}
return 0;//정상종료시 반드시 0을 리턴해야합니다.
}
음 우선순위 큐 구현해서 했는데 왜 틀리는지 모르겠다...
#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
class Heap {
private :
int Size=0;
int arr[100001] = { 0 };
void swap(int *a, int *b);
public:
int front();
void push(int x);
int pop();
int size();
void clear();
};
void Heap::clear() {
Size = 0;
return;
}
int Heap::size() {
return Size;
}
void Heap::swap(int *a, int *b) {
int tmp;
tmp = *a;
*a = *b;
*b = tmp;
}
int Heap::front() {
return arr[1];
}
void Heap::push(int x) {
Size++;
arr[Size] = x;
int cur = Size;
while (cur != 0 && arr[cur / 2] > x) {
swap(&arr[cur / 2], &arr[cur]);
cur = cur / 2;
}
}
int Heap::pop() {
int ans = arr[1];
arr[1] = arr[Size];
Size--;
int cur = 1;
while (1) {
int smaller = arr[2*cur + 1] > arr[2*cur] ? 2*cur : 2*cur+1;
if (arr[cur] > smaller) {
swap(&arr[cur], &arr[smaller]);
}
else {
break;
}
}
return ans;
}
int N, K;
vector<int> arr;
int main(int argc, char** argv)
{
int test_case;
int T;
//freopen("input.txt", "r", stdin);
cin >> T;
for (test_case = 1; test_case <= T; ++test_case)
{
cin >> N >> K;
arr.clear();
for (int i = 0; i < N; i++) {
int tmp;
cin >> tmp;
arr.push_back(tmp);
}
int maxv = 0;
for (int k = 0; k < N; k++) {
Heap hp;
hp.clear();
hp.push(arr[k]);
for (int j = k+1; j < N; j++) {
if (arr[j] - hp.front() <= K) {
hp.push(arr[j]);
}
}
if (maxv < hp.size()) {
maxv = hp.size();
}
}
cout <<"#"<< test_case<<" "<< maxv<<"\n";
}
return 0;//정상종료시 반드시 0을 리턴해야합니다.
}
8998. 세운이는 내일 할거야
이제부터는 iostream만 사용해야 겠다. 링크드 리스트를 주로 사용한다 했다.
숙제하는데 걸리는 시간 t, 마감일 d가 주어졌을때 적어도 몇일째 X에는 숙제를 시작해야하는 문제이다.
과제 수는 10^6 까지 주어져서 nlogn안에 풀어야 한다. X>=0 이라 한다.
어떻게 푸는지 모르겠다. 1~10^6일을 일일이 체크하면 n^2이라 안된다.
일일이 체크하는 방법 밖에 모르겠다.
아 음 이분 탐색으로 하면 되려나? 그리고 확인은 마감날이 촉박한거 먼저 해야 될거 같다.
즉 정렬을 구현해야한다... 퀵정렬로 해보자.
음 배열 클래스 만들어서 했는데 arr[1000001]이 스택 오버플로우가 일어난다.
#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
using namespace std;
typedef struct elems {
int a, b;
};
elems arr[1000001];
class Array{
private:
int size=0;
public:
void quick_sort_inc(int st, int dt);
void swap(elems *a, elems *b);
void push(elems x);
};
int maxv;
void Array::push(elems x) {
size++;
arr[size] = x;
}
void Array::swap( elems *a,elems*b) {
elems tmp;
tmp = *a;
*a = *b;
*b = tmp;
}
void Array::quick_sort_inc(int st, int dt) {
int pivot =st;
int i = st+1;
int j = dt;
if (st >= dt)
return;
while(i<=j) {
while (arr[pivot].b > arr[i].b && i<=dt) {
i++;
}
while(arr[pivot].b < arr[j].b && j>=st) {
j--;
}
if (i > j) {
swap(&arr[pivot], &arr[j]);
}
else {
swap(&arr[i], &arr[j]);
}
}
quick_sort_inc(st, j - 1);
quick_sort_inc(j + 1, dt);
}
int N;
int main(int argc, char** argv)
{
int test_case;
int T;
// freopen("input.txt", "r", stdin);
cin >> T;
for (test_case = 1; test_case <= T; ++test_case)
{
cin >> N;
int last_due=1000000001;
Array A;
for (int i = 0; i < N; i++) {
elems tmp;
int a, b;
cin >> a >>b;
tmp.a = a;
tmp.b = b;
if (last_due > b)
last_due = b;
A.push(tmp);
}
A.quick_sort_inc(1,N);
for (int i = 0; i < last_due; i++) {
int cur_day = i;
for (int j = 1; j <= N; j++) {
cur_day += arr[j].a;
if (cur_day <= arr[j].b) {
if (j == N) {
maxv = i;
}
else
continue;
}
else {
i = last_due;
break;
}
}
}
cout <<"#"<< test_case<<" "<< maxv<<"\n";
}
return 0;//정상종료시 반드시 0을 리턴해야합니다.
}예제만 맞고 시간초과가 난다.
D가 적었으면 상관없는데 커서 이중 반복문으로 하면 안된다....
A.quick_sort_inc(1, N);
//last_due가 1~10^9 이라 여기서 시간 초과가 발생한다.
for (int i = 0; i < last_due; i++) {
int cur_day = i;
//N은 1~10^6......아
for (int j = 1; j <= N; j++) {
cur_day += arr[j].a;
다시 원점에서 생각해 보자.
3
2 8
1 13
3 10
결국 구해야 되는건
이 숙제는 2 - 8 = 6 일에는 시작해야되
이 숙제는 1 - 13 = 12 일에는 시작해야되
이 숙제는 3 - 10 = 7일에는 시작해야되.
6,7,12 중에 가장 작은 값인 6에서 최소한 시작해야 되는데
얼마나 더 먼저 시작해야 될까.
6일에 숙제를 시작하면 2일 더해서 8일이 되고,그 다음 숙제는 3일 걸리고 10일까지 해야 되는 숙제가 총 11일이 걸린다.
6 일에 시작해서 숙제 2일 더하면 8일이 된다.
8일에 3일 숙제를 하면 11일 (10<11으로 ) 11- 10 만큼 시작일 6에서 나중에 빼게 1만큼 decrease에 저장한다.
10일에 숙제를 1일 하면 11일 (11<12) 므로 그냥 패스.
음 위처럼 구현하고 퀵소트도 다시 고쳤는데 14개중에 7개만 패스했다......... 시간 초과가 발생했다.
#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
using namespace std;
typedef struct elems {
int a, b;
};
elems arr[1000001];
class Array {
private:
int size = 0;
public:
void quick_sort_inc(int st, int dt);
void swap(elems *a, elems *b);
void push(elems x);
void clear();
};
int maxv;
void Array::clear() {
size = 0;
}
void Array::push(elems x) {
size++;
arr[size] = x;
}
void Array::swap(elems *a, elems*b) {
elems tmp;
tmp = *a;
*a = *b;
*b = tmp;
}
void Array::quick_sort_inc(int i, int j) {
int pivot = i;
int left = i;
int right = j;
if (i >= j)
return;
while (left <= right) {
while (arr[pivot].b > arr[left].b) {
left++;
}
while (arr[pivot].b < arr[right].b) {
right--;
}
if (left <= right) {
swap(&arr[left], &arr[right]);
left++; right--;
}
}
quick_sort_inc(i, right);
quick_sort_inc(left, j);
}
int N;
int main(int argc, char** argv)
{
int test_case;
int T;
freopen("input.txt", "r", stdin);
cin >> T;
for (test_case = 1; test_case <= T; ++test_case)
{
cin >> N;
int start_due = 1000000001;
Array A;
A.clear();
for (int i = 0; i < N; i++) {
elems tmp;
int a, b;
cin >> a >> b;
tmp.a = a;
tmp.b = b;
if (start_due > b-a)
start_due = b-a;
A.push(tmp);
}
A.quick_sort_inc(1, N);
int cur_day = start_due;
int decrease=0;
for (int i = 1; i <= N; i++) {
cur_day = cur_day + arr[i].a;
int limit = arr[i].b;
if (limit < cur_day) {
int dis = cur_day - limit;
decrease += dis;
cur_day -= dis;
}
}
maxv = start_due - decrease;
cout << "#" << test_case << " " << maxv << "\n";
}
return 0;//정상종료시 반드시 0을 리턴해야합니다.
}
음 도대체 왜 안되는 걸까..
2 8
2 8
3 19
1 13
아 내가 짠 퀵소트 말고 라이브러리 사용하니까 된다. ㅋㅋ아 ㅋㅋ
#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
typedef struct elems {
int a, b;
};
//elems arr[1000001];
vector<elems>arr;
bool cmp(elems a, elems b)
{
if (a.b < b.b) { return true; }
else return false;
}
class Array {
private:
int size = 0;
public:
void quick_sort_inc(int st, int dt);
void swap(elems *a, elems *b);
void push(elems x);
void clear();
};
int maxv;
void Array::clear() {
size = 0;
}
void Array::push(elems x) {
size++;
arr[size] = x;
}
void Array::swap(elems *a, elems*b) {
elems tmp;
tmp = *a;
*a = *b;
*b = tmp;
}
void Array::quick_sort_inc(int i, int j) {
int pivot = i;
int left = i;
int right = j;
if (i >= j)
return;
while (left <= right) {
while (arr[pivot].b > arr[left].b) {
left++;
}
while (arr[pivot].b < arr[right].b) {
right--;
}
if (left <= right) {
swap(&arr[left], &arr[right]);
left++; right--;
}
}
quick_sort_inc(i, right);
quick_sort_inc(left, j);
}
int N;
int main(int argc, char** argv)
{
int test_case;
int T;
//ios_base::sync_with_stdio(false);
ios_base::sync_with_stdio(false);
// freopen("input.txt", "r", stdin);
cin >> T;
for (test_case = 1; test_case <= T; ++test_case)
{
cin >> N;
int start_due = 1000000001;
arr.clear();
for (int i = 0; i < N; i++) {
elems tmp;
int a, b;
cin >> a >> b;
tmp.a = a;
tmp.b = b;
if (start_due > b-a)
start_due = b-a;
arr.push_back(tmp);
}
sort(arr.begin(), arr.end(), cmp);
//A.quick_sort_inc(1, N);
int cur_day = start_due;
long long int decrease=0;
for (int i = 0; i < arr.size(); i++) {
cur_day = cur_day + arr[i].a;
int limit = arr[i].b;
if (limit < cur_day) {
int dis = cur_day - limit;
decrease += dis;
cur_day -= dis;
}
}
maxv = start_due - decrease;
cout << "#" << test_case << " " << maxv << "\n";
}
return 0;//정상종료시 반드시 0을 리턴해야합니다.
}
8993. 하지 추측
하지 추측 ....
while (N > 1){
if (N mod 2 == 0) N := N / 2
else N := 3 * N + 3
}과연 이게 주어진 자연수 N에 대해 종료 될까 그게 문제다. 코드 안을 보니 그냥 2의 거듭제곱수로 한번만 바뀌면 if에 의해서 끝나버린다. 즉 3*N+3으로 주어진 N이 2의 거듭제곱이 될 수 있을것인가?
사실 N이 2^n + k이면 3*(2^n +k ) +3 -> 3*2^n + 3k + 3 -> 3k+3이 2^n의 수이고 3 + (3k+3)/2^n이 2의 거듭제곱이면 되나?
음 이건 아닌거 같고
예제의 3,4를 넣어보니 3 은 3 -> 12 -> 6 -> 3 즉 반복된다. 주어진 N이 (1 ≤ N ≤ 10^14) 라서
반복되는지 확인하는 배열을 만드는 것도 무리이다.... 음 ㅋㅋ?...
5도 넣어 보자. 5 -> 18 -> 9 -> 30 -> 15 ->48 ->24 ->12 ->6 ->3 ->12 -> 6 -> 3....
해쉬 테이블에 넣고 같은거 나오면 안된다. 하는 쪽이 날거 같다.?
음 구현했는데 31개중 16개인가 맞았다. 그냥 오답임.
#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
using namespace std;
typedef struct Node {
int val;
Node *next = NULL;
};
class Hashmap {
private:
struct Node hash[10000];
int base = 10000;
public:
void insert(int x);
bool find(int x);
};
void Hashmap::insert(int x) {
int index = x % base;
Node* cur = hash[index].next;
if (cur == NULL) {
/*
Node*newNode = new Node;
cur = newNode;
cur->val = x;
return;
*/
Node* newNode = new Node;
hash[index].next = newNode;
hash[index].next->val = x;
return;
}
while (cur != NULL) {
cur = cur->next;
}
Node* newNode = new Node;
cur = newNode;
}
bool Hashmap::find(int x) {
int index = x % base;
Node* cur = hash[index].next;
while (cur != NULL) {
if (cur->val == x) {
return true;
}
cur = cur->next;
}
return false;
}
int N;
int main(int argc, char** argv)
{
int test_case;
int T;
freopen("input.txt", "r", stdin);
cin >> T;
string ans ="";
for (test_case = 1; test_case <= T; ++test_case)
{
Hashmap HM;
cin >> N;
HM.insert(N);
ans = "YES";
while (N > 1) {
if (N % 2 == 0) {
N = N / 2;
if (HM.find(N)) {
ans = "NO";
break;
}
HM.insert(N);
}
else {
N = 3 * N + 3;
if (HM.find(N)) {
ans = "NO";
break;
}
HM.insert(N);
}
}
if(ans=="YES")
cout << "#" << test_case << " " << "YES" << "\n";
else
cout << "#" << test_case << " " << "NO" << "\n";
}//for
return 0;//정상종료시 반드시 0을 리턴해야합니다.
}왜 오답이지이 아 일단 long long int로 바꿔야한다.
그리고
1
100000000000001 이걸 넣으니까 계속 증가하기만 한다......아 제한을 어떻게 둬야 되지? 그냥 너무 커지면 안된다고 제한 두니까 맞았다. ㅋㅋㅋㅋ이런
#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
using namespace std;
typedef struct Node {
long long int val;
Node *next = NULL;
};
class Hashmap {
private:
struct Node hash[10000];
int base = 10000;
public:
void insert(long long int x);
bool find(long long int x);
};
void Hashmap::insert(long long int x) {
int index = x % base;
Node* cur = hash[index].next;
if (cur == NULL) {
/*
Node*newNode = new Node;
cur = newNode;
cur->val = x;
return;
*/
Node* newNode = new Node;
hash[index].next = newNode;
hash[index].next->val = x;
return;
}
while (cur != NULL) {
cur = cur->next;
}
Node* newNode = new Node;
cur = newNode;
}
bool Hashmap::find(long long int x) {
int index = x % base;
Node* cur = hash[index].next;
while (cur != NULL) {
if (cur->val == x) {
return true;
}
cur = cur->next;
}
return false;
}
long long int N;
int main(int argc, char** argv)
{
int test_case;
int T;
freopen("input.txt", "r", stdin);
cin >> T;
string ans ="";
for (test_case = 1; test_case <= T; ++test_case)
{
Hashmap HM;
cin >> N;
HM.insert(N);
ans = "YES";
int cnt = 0;
while (N > 1) {
cnt++;
if (cnt > 10 && N > 100000000000001)
{
ans = "NO";
break;
}
if (N % 2 == 0) {
N = N / 2;
if (HM.find(N)) {
ans = "NO";
break;
}
HM.insert(N);
}
else {
N = 3 * N + 3;
if (HM.find(N)) {
ans = "NO";
break;
}
HM.insert(N);
}
}
if(ans=="YES")
cout << "#" << test_case << " " << "YES" << "\n";
else
cout << "#" << test_case << " " << "NO" << "\n";
}//for
return 0;//정상종료시 반드시 0을 리턴해야합니다.
}
시간은 6ms로 양호한데 3ms인 분 코드르 보니까 비트 연산을 이해하지 못하겠다.....
#include <stdio.h>
int main() {
int t = 0, T;
char* ans1 = "#%d NO\n";
char* ans2 = "#%d YES\n";
scanf("%d", &T);
while (t ^ T) {
long long N;
scanf("%lld", &N);
if (N & -N ^ N) printf(ans1, ++t);
else printf(ans2, ++t);
}
}'알고리즘 문제 풀기' 카테고리의 다른 글
| 프로그래머스 - 정렬 : K번째 수, 가장 큰 수, H index (0) | 2020.01.13 |
|---|---|
| swexpertacademy - 1768. 숫자야구게임 (0) | 2020.01.08 |
| 프로그래머스 - 힙 : 더 맵게,라면 공장, 디스크 컨트롤러 (0) | 2020.01.05 |
| 프로그래머스 - 카카오 2018 블라인드 테스트 (추석 트래픽) (0) | 2020.01.04 |
| 백준 - 1725번 히스토그램,6549 히스토그램에서 가장 큰 직사각형 (0) | 2020.01.03 |