Hoon222y

https://www.acmicpc.net/problem/1744 그리디 문제이다. 문제의 함정은 1) 양수는 양수끼리 2) 음수는 음수끼리 3) 1은 되도록 묶지 말아야 한다. 4) 0은 묶지 않는것이 최대 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566#include #include #include #include #include #include #include #include #include #include #define INF 1e9typedef long long ll;using namespace std; ll ans, n,a..

https://www.acmicpc.net/problem/1781 그리디인것처럼 보이고 그리디로 풀면된다 .그냥 정렬하고 최대값만 뽑았다가 개망한건 눈물 .. 주의할점은 큐에 넣어주면서 데드라인에 맞게 정답 큐 사이즈를 조절해 주면 된다는것이다. 12345678910111213141516171819202122232425262728293031323334353637383940414243#include #include #include #include #include #include #include #include #include #include #define INF 1e9typedef long long ll;using namespace std; priority_queue pq;int n,a,b;vector v..

lower_bound 와 upper_bound 모두 정렬되어진 컨테이너에서 원하는 값을 찾는것이다. 즉 먼저 정렬이 되어있다는것이 기본이다. 이 두함수는 비슷한듯 차이가 있는데 1. lower_bound - 반환값이 이터레이터이므로 원하는 index를 반환받기 위해서는 distance(v.begin(), lower_bound())를 통해 인덱스를 반환2. upperr_bound - 반환값이 이터레이터이므로 원하는 index를 반환받기 위해서는 distance(v.begin(), upper_bound())를 통해 인덱스를 반환 이 둘의 차이점은 바로 둘다 binary search를 통해서 값을 찾아주기는 하지만lower_bound는 value를 포함한 이상인 값을 , upper_bound는 value를 포..

https://www.acmicpc.net/problem/3273 단순이 찾아보면 n이 10만이기 때문에 O(N^2)으로 시간초과정렬된 배열에서 binary search를 해아한다. 포스팅 하는 이유는 STL binary_search를 처음 써봐서 ;; 1234567891011121314151617181920212223242526272829303132333435363738#include #include #include #include #include #include #include #include #include #include #define INF 1e9typedef long long ll; using namespace std; int n,ans,x;vector v; int main(){ cin >>n..

https://www.acmicpc.net/problem/11058 해당 문제의 경우 DP로 접근을 한다. DP 테이블을 dp[i] = i번째 화면에 출력되는 최대 A의 개수 라고 정의를 한 다음 문제에 접근한다. 이 문제의 포인트는 1) i가 7을 넘어가면 버퍼에 있는 것을 복사하는 것이 최대가 된다.2) 정답은 int의 범위를 넘어간다는 것 (주의) 따라서 버퍼에 들어가기 위해서는 Ctrl +A, Ctrl + C, Ctrl + V 가 필수이므로 버퍼에 들어가는 경우의 점화식은 dp[i] = max(dp[i],dp[i-3]*2) 부터 시작하게 된다. 1234567891011121314151617181920212223242526272829303132333435#include #include #includ..

https://www.acmicpc.net/problem/13700 그냥 bfs문제이다 하지만 주의해야 할 점은 next+f 0 이어야 한다는 점이다 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960#include #include #include #include #include #include #include #include #include #define INF 1e9typedef unsigned long long ull; using namespace std; int n,s,d,f,b,k,arr[111111];bool visit[111111]; void s..

Normal ver 123456789101112int gcd(int x,int y){ if(x>y){ swap(x,y); } while(y!= 0){ int r = x%y; x=y; y=r; } return x;} cs 재귀함수 ver1234567int gcd(int x,int y){ if(y == 0){ return x; }else{ return gcd(y,x%y); }}cs

https://www.acmicpc.net/problem/1377 버블 소트가 총 몇 회 발생하는지 찾는 문제이다. 하지만 그냥 실제로 버블 소트를 하면서 버블 소트 횟수를 찾게되면 N의 제한이 50만이고 복잡도가 O(N^2)이므로 시간초과이다. 이 문제의 경우 버블 소트의 특성을 잘 이해하면 풀 수 있는 문제이다. 버블 소트의 경우 한번 반복될 때 오른쪽으로는 몇번을 이동하게 되던, 왼쪽으로는 어떤 수이던 딱 한번만 움직이게 된다. 따라서 처음 입력에서 sort한 이후에 인덱스의 차이가 가장 큰 경우를 찾아주면 되는 문제이다. 12345678910111213141516171819202122232425262728293031323334#include #include #include #include #inc..

https://www.acmicpc.net/problem/2602 발은 두개니까 두발로 두줄의 돌다리를 건너는 문제이다 (규칙은 문제를 읽어보도록 ...)해당 문제의 경우 dp테이블을 3차원으로 dp[위쪽인지 아래쪽인지][몇번째 문자열인지][몇번째로 밟았는지] 로 정의할 수 있다. 간략하게 dp점화식을 세운다면 dp[위쪽][i번쨰 문자열][j번쨰로 밟은경우] += dp[아래쪽][i-1번째 문자열][j-1번쨰로 밟은경우] 이런식이다. 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758#include#include#include#include#include#includ..