Hoon222y

https://www.acmicpc.net/problem/14699 쉼터에서 높은 곳으로만 이동이 가능할 때 각 쉼터에서 가장 많이 들릴수 있는 경우를 찾는 문제이다.그냥 BFS를 톨리게 되면 시간초과가 나는데 왜나는지는 정확히 모르겠다 ㅠ 누가 설명좀 ;;; (그래서 계속틀림)다른 방법으로는 DFS를 재귀적으로 접근하는 방법이었는데 나는 그렇게 안하고 위상정렬을 이용하였다. 일단 쉼터들끼리 연결을 해주고, 그 이후에 자신으로 들어오는 간선이 없는 경우를 배열에 채워주는 방식으로 접근하였다. 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646..

https://www.acmicpc.net/problem/1939 주어진 도로의 중량제한을 넘어서지 않는 배달가능한 최대물품중량을 계산하는문제이다.BFS와 이분탐색을 이용해서 문제를 해결하면 된다. 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374#include #include #include #include #include #include #include #include #include #include #define INF 1e9typedef long long ll;using namespace std; i..

https://www.acmicpc.net/problem/1854 k번째 최단경로를 찾는 문제이다. 보통 최단경로 문제를 풀게되면 다익스트라를 이용해서 접근하는 것처럼 이 문제 또한 다익스트라를 기반으로 한다. 하지만 그냥 다익스트라와 조금 차이가 있다면 dist배열을 그냥 dist[i] = 시작점에서 i 번 점으로 갈 때 걸리는 최단거리로 정의하는 것이 아니라 dist를 queue+배열로 정의하여 dist[i][j]는 i번 지점으로 갈 때 j번째 최단거리라고 정의를 하고 문제를 접근하게 된다. (17번째 줄) 즉 포인트는1) 다익스트라 배열을 항상 k개의 최단경로를 저장하게 만든다. 2) 저장된 경로가 k번보다 작을떄는 최단경로를 그냥 push해주고 3) 저장된 경로가 k번보다 크거나 같을때는 가장 큰..

https://www.acmicpc.net/problem/1944 해당 문제의 경우 시작점과 키가 있는 지점간의 모든 거리를 구해두고 MST를 만들면 된다. 여기서 주의해야 할 점은 1) S와 K에서만 복제가 가능하기 때문에 57번째 줄 처럼 각각의 거리를 구할 때 K나 S에 도달했을 때에도 Queue에 넣어줘야 한다.2) 배열의 크기는 M이다 .... 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586878889909192939495969798991001011021..

https://www.acmicpc.net/problem/2211 처음 문제 조건 1번을 읽고 2번을 읽은 후, MST를 하는 과정에서 다익스트라로 제한을 걸면서 MST를 만들면 되는줄 알았는데 개 망 ... 해매다가 Q&A 에서 본 것을 통해 그냥 단순 다익스트라로 풀 수 있다고 알게 되었다 (근데 아직 정확히 와닿지는 않음 ..) 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374#include #include #include #include #include #include #include #include..

https://www.acmicpc.net/problem/2887 모든 행성이 연결되는 MST를 만드는 문제이다. 하지만 보통 구하느 MST와는 다르게 N의 제한이 10만이기 때문에 모든 간선의 길이를 다 넣어주게 되면 O(N^2)으로 시간초과&메모리 초과 콤비를 맞게 될 것이다. 따라서 간선을 넣어줄 때 필요한 부분만 넣어주는 처리가 필요하다. 핵심은 거리가 Min(x절대값 차이, y절대값 차이, z절대값 차이) 이므로 각각 x,y,z를 기준으로 sort해준 다음 인전한 경우에만 거리를 넣어주는 3N의 시간복잡도를 넣어주게 되면 해결할 수 있다. 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484..

https://www.acmicpc.net/problem/6496497 MST를 만드는 문제이다.총 길이에서 MST를 만든 후 그 경로의 길이를 뺴주면 절약한 길이를 얻을 수 있다. 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162#include #include #include #include #include #include #include #include #include #include #define INF 1e9typedef long long ll;using namespace std; ll ans,t,n,m,parent[211111];vector..

https://www.acmicpc.net/problem/1946 정렬 후 그리디 적으로 접근을 하면 된다.n의 제한이 크기 떄문에 완전탑색식의 비교는 안되고 첫번째 성적을 기준으로 정렬을 한 뒤 2번째부터 n번째가지 최대 성적을 갱신해 주는 방식을 사용한다. 1234567891011121314151617181920212223242526272829303132333435363738394041424344#include #include #include #include #include #include #include #include #include #include #define INF 1e9typedef long long ll;using namespace std; int t,n,ans; vector v; int..

https://www.acmicpc.net/problem/2458 자신으로 올 수 있는 지점 + 자신이 갈 수 있는 지점 = n-1 일 경우 자신의 순위를 알 수 있다. n의 범위가 500까지 이므로 플로이드 워셜을 사용하였다. 근데 O(N^3)인데 1초안에 어케 들어오는거지 ?;;;; 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455#include #include #include #include #include #include #include #include #include #include #define INF 1e9typedef long long ll;using name..

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