Mini

https://www.acmicpc.net/problem/2018* 시도1누적합만들고이진탐색으로 찾으면 될듯?메모리초과 (1천만배열)시간초과 (n log 1천만 ) == 천만 * 23 -> 23억o(N)에 풀어야한다. * 풀이이문제는 메모리제한이 32MB -> 1천만 배열불가능s,e가 index인 동시에, 값의 역할도 해야함!엣지케이스 확인n=1 ) break문에 걸려서 잘처리됨마지막 부분 해보기break에 걸려서 자기자신이 카운팅이 안됨 -> ret=1 로 시작#includeusing namespace std; typedef long long ll;ll n,ret;int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin>..

* 완탐-내코드{차이, idx}를 저장하고차이로정렬하고, idx로 원본에 다시접근하는방법매우 비효율적임.class Solution {public: static bool cmp(pair p1, pair p2){ if(p1.first==p2.first){ //인덱스작은거우선 return p1.second findClosestElements(vector& arr, int k, int x) { vector> gabs; //{차이, 인덱스} for(int i=0;i ret; for(int i=0;i- 정답코드굳이 idx를 저장할필요없이 차이로 원본배열을 정렬해버리면됨.class Solution {public: vector findCl..

https://www.acmicpc.net/problem/22988 22988번: 재활용 캠페인 첫 번째 용기와 두 번째 용기를 가져가서 용량이 $\left(0+1+\frac{13}{2}\right)$㎖ $=$ $7.5$㎖ 남은 용기를, 세 번째 용기와 네 번째 용기를 가져가서 용량이 $\left(2+3+\frac{13}{2}\right)$㎖ $=$ $11.5$㎖ 남은 용 www.acmicpc.net 1. 의사코드 1. n이 10만 -> 완탐불가 -> 투포? 2. s와 e를 움직이며 관찰한다. 3. e가 이미 x이상인경우-> 가능성없음 -> 제거, cnt+1 4. 병을만들수있으면 만든다. (코드참조) 5. 병을못만드는 경우 -> s+1 -> 더큰값과 합치면 병을 만들수 있는지 탐색한다. 5.1. 위에서 ..

https://www.acmicpc.net/problem/16472 16472번: 고냥이 고양이는 너무 귀엽다. 사람들은 고양이를 너무 귀여워했고, 결국 고양이와 더욱 가까워지고 싶어 고양이와의 소통을 위한 고양이 말 번역기를 발명하기로 했다. 이 번역기는 사람의 언어를 고 www.acmicpc.net 1. 시행착오 1. cnt에 e-1과 e를 비교하여 다르면 cnt를 1증가시킨다. 반례 : cac의 경우 실제 cnt는 2가 되어야하는데, 단순히 e와 e-1을 비교하면 ac에서 a!=c이므로 cnt가 증가되어 버린다.. 2. 해결 : set에 현재 등장한 알파벳들을 저장한다 2. 의사코드 1.while(str의 범위내인지 체크) 2. 현재 알파벳갯수가 n이하인경우 -> 너 가능성있어 -> e를 뒤로보내며..

https://www.acmicpc.net/problem/2470 2470번: 두 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 2 이상 100,000 이하이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 수들은 모두 -1,000,000,000 이상 1,000,00 www.acmicpc.net 1. 의사코드 1.1 st,en중 누구를 움직일지 결정하라 if (sum1 커져야함->음수를 줄임 -> st++ else e--; //합이양수 -> 작아져야함 -> 양수를 줄임 -> e++ 1.2 변수 테이블을 정의하라 //ret : 현재까지 값중 0에 가장가까운 합 2. 전체코드 #include using namespace st..

https://www.acmicpc.net/problem/20922 20922번: 겹치는 건 싫어 홍대병에 걸린 도현이는 겹치는 것을 매우 싫어한다. 특히 수열에서 같은 원소가 여러 개 들어 있는 수열을 싫어한다. 도현이를 위해 같은 원소가 $K$개 이하로 들어 있는 최장 연속 부분 수열 www.acmicpc.net 1. 전체코드 #include using namespace std; typedef long long ll; ll n, k,ret,temp; vector v; int vis[1000000 + 1];//해당숫자 방문했는지 여부 int main() { ios::sync_with_stdio(0); cin.tie(0); cin >> n>>k; for (int i = 0; i < n; ++i) { ci..

https://www.acmicpc.net/problem/22862 22862번: 가장 긴 짝수 연속한 부분 수열 (large) 수열 $S$에서 최대 $K$번 원소를 삭제한 수열에서 짝수로 이루어져 있는 연속한 부분 수열 중 가장 긴 길이를 출력한다. www.acmicpc.net 1. 의사코드 holsu변수를 db로 사용한다. holsu변수 => s~e까지 구간중 홀수의 갯수를 저장, 갱신한다. 2. 전체코드 #include using namespace std; typedef long long ll; ll n, k,ret,temp; vector v; int vis[1000000 + 1];//해당숫자 방문했는지 여부 int main() { ios::sync_with_stdio(0); cin.tie(0); ..

https://www.acmicpc.net/problem/13144 13144번: List of Unique Numbers길이가 N인 수열이 주어질 때, 수열에서 연속한 1개 이상의 수를 뽑았을 때 같은 수가 여러 번 등장하지 않는 경우의 수를 구하는 프로그램을 작성하여라.www.acmicpc.net1. 배열활용 아이디어vis[해당숫자] 방문여부표시 => 중복숫자인지 검사 2.전체코드#include using namespace std;typedef long long ll;ll n, m,ret,temp;vector v;int vis[1000000 + 1]; //해당숫자 방문했는지 여부int main() { ios::sync_with_stdio(0); cin.tie(0); cin >> n; for (int ..