Hoon222y

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..

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..

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..

https://www.acmicpc.net/problem/14431 해당 문제의 경우 점의 거리가 소수일 경우 움직일 수 있고, 시작점에서 도착점으로 최소의 경로로 이동하는 문제이다. 문제의 가장 큰 핵심은 먼저 소수들을 에라토스테네스를 이용하여 먼저 구하고 각 정점들이 소수인 거리일 때 각 점들을 이어주고 다익스트라를 수행하면 된다. 모든 정점을 이어준다음 판별한다고 생각을 처음 했었는데 ... ㅋㅋ... 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687#in..

https://www.acmicpc.net/problem/13911 해당문제의 경우 맥세권과 스세권의 최소거리를 구하는 문제이다. 그냥 다익스트라를 하면 되는 문제이지만 이 문제의 경우 V의 범위가 10000까지이므로 집에서 다 구하는경우 당연히 시간초과.해결 방법은 집들에서 다익스트라를 돌리는것이 아니라 그냥 스벅들과 맥도날드 지점에서 다익스트라를 돌려서 각 집까지 거리가 얼마나 되는지 구하면 되는 문제이다. 해당문제의 경우 생각보다 아이디어 떠올리는데는 시간이 얼마 안걸렸지만 11번의 WA;;; 음 .그 실수한 부분은... 바로 스벅에서 집을 갈 때 스벅->집-> 집..-> 도착 이것이 아니라 맥도날드를 거쳐서 가는 경우가 더 빠를수 있다는 것이다. 일단 코드를 첨부하면 1234567891011121..

http://codeforces.com/contest/816/problem/B n개의 구간정보와 q개의 정보가 있을 때 k개 이상인 부분의 개수를 뽑문 문제이다.해당문제의 경우 n,q의 범위가 20만이기 때문에 직접전부다 해주면 시간 초과데스 일단 n개의 범위를 체크하는 테크닉 하나 예를들어 n개의 범위들을 체크할 때 시작점을 +1 , 마지막점+1인 부분을 -1로 배열에 전처리를 해준다. 예시인 (91 94), (92,97) , (97,99) 91 92 93 94 95 96 97 98 99 100 +1 -1 +1 -1 +1 -1 이라고 배열에 전 처리를 해주는것이다.그리고 배열을 부분 합 구해준다. 91 92 93 94 95 96 97 98 99 100 1 2 2 2 1 1 2 1 1 0 이라고 구해주면..

https://www.acmicpc.net/problem/12869 그냥 디피를 통해서 시간을 줄이는 것이다.이문제 작성하는 이유는 .. min({,,,,})을 통해서 최소값 구하는 코드를 간략히 배울수 있다는 점에서 첨부한다. 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263#include#include#include#include#include#include#include#include#include#include#define INF 1e8 using namespace std;int n,v[3],minv,dp[66][66][66]; int s..