Hoon222y

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

https://www.acmicpc.net/problem/3062 위 문제처럼 string 과 int 형변환이 필요할때여기서의 테크닉은 1.string에도 push_back이 된다!!2.stoi 와to_string 123456789101112131415161718192021222324252627282930313233343536373839404142#include#include#include#include#include#include#include#include#include#include#define INF 1e5typedef long long ll; using namespace std; int main(){ int num1, num2, result; string b; string c = ""; stri..

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 이라고 구해주면..

dp를 하면서 최소값을 넣어주는 경우가 있는데 그럴떄는 min({,,,,})를 사용하면 깔끔해진다. 12 return ret= min({solve(a-9,b-3,c-1),solve(a-9,b-1,c-3),solve(a-3,b-1,c-9),solve(a-3,b-9,c-1),solve(a-1,b-9,c-3),solve(a-1,b-3,c-9)})+1; Colored by Color Scriptercs 이런식으로 ..

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

https://www.acmicpc.net/problem/2110 공유기를 c 개 이상 설치하는데 그 간격이 가장 크게 배치하는 방법이다.이 문제의 경우 핵심은 "답을 x라고 가정할 때 그 답이 가능한가?" 라는 질문에 답을하는것이다. 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647#include#include#include#include#include#include#include#include#include#include using namespace std; int n,c;int main(){ scanf("%d%d" , &n,&c); vector v(n); for(int i=0;i

https://www.acmicpc.net/problem/9466dfs의 사이클을 체크하여 사이클의 경우 dfs를 돌리지 않고 최적화 하는 방법으로 시간을 줄이는 문제이다. 찬란한 오답 퍼레이드 ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋdfs상에서 사이클을 체크하는 방법은 아직 끝나지 않았지만 visit된 정점을 방문할경우 사이클이 존재한다고 생각하는 것이다. 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354#include#include#include#include#include#include#include#include#include#include using namespace std; ..

https://www.acmicpc.net/problem/1300 N*N크기의 배열에서 k번째 수를 구하는 문제이다. N의크기가 10^5까지이기 때문에 배열을 실제로 할당하는것은 메모리 초과 -> 터짐 따라서 다른 방법을 생각해 보아야 한다. 이 문제의 핵심은 parametric search를 이용하는 것이다. 정답이 0과 N*N 사이의 한 정수이기 때문에 이분탐색방식을 이용하여 접근한다. 핵심은 임의의 수를 답이라고 가정하고, 그 수가 k번쨰 수인지 확인하는 방식이다. 여기서 k번째 수라는 뜻은 자기보다 작은 숫자가 k-1개라는 뜻임을 기억하자. 12345678910111213141516171819202122232425262728293031323334353637383940#include #include..

https://www.acmicpc.net/problem/1194 bfs를 이용하여 문제를 해결하는 문제이다. 해당 문제를 풀때 고민해야하는 점이 있다면 어떤점을 이동할때 , 그리고 방문할때 다른 bfs처럼 visit 처리를 해주어야 하는데 그때마다 어떤 열쇠들을 가지고 있는지 그떄의 열쇠상태를 가지고 있어야 한다는 점이다. 하지만 bfs특성상 while문 내에 키의 상태를 가지고 있는 배열 혹슨 백터들을 가지고 실행한다는 것은 메모리 초과로 이어지게 된다.따라서 이러한 경우 필요한 테크닉은 비트마스크를 이용한 처리이다. 문제의 접근 핵심을 정리하자면 (1) 열쇠는 6종류만 가지고 있다. (2) 어떤 지점을 방문할때 visit처리를 위해 visit배열의 선언을 visit[어떠한 열쇠를 가지고 있는지 비트..