나 요리학원 출신임

시작점에서 끝점까지 가는데 가장 긴 경로를 출력하고 그때 지나가는 길의 수출력하는 문제다..! 가장 긴 경로 구하는건 쉬웠는데 지나온 길 찾는게 어려워따 ㅎㅎ백준의 도움을 받아따 ㅎㅎ 문제는 위상정렬을 이용해서 풀었다! 위상정렬로 가장 긴 경로는 d[next] = max(d[next] , d[here]+cost)로 구할 수 있다 그리고 지나온 경로는 역으로 그래프를 만들어서 방문한 점중에 가장 긴 경로와 지나온 거리가 같다면 카운트를 올리는 식으로 했다! DAG에서 가장 긴 경로 구하는 문제로 기억해둬야지 ㅎㅎ 소스코드123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657..

정점 N개, 간선 N-1개 트리가 주어지고 루트를 알려준다.그리고 루트에서 리프노드로 가면 탈출 가능할 때리프노드에 탈출을 막는 사람을 몇명 둬야하는지 찾는 문제이다. 탈출을 막는 사람과 탈출 하려는 사람의 속도는 같다. 처음에 시도한 방법은 dfs를 돌려서 리프노드에 도착했을 때 루트와 가장 가까운 두갈래 이상의 길을 찾아서 그 정점에 거리를 넣었다.그리고 마지막에 정점을 다 보며 거리가 들어있으면 루트에서 그 정점까지 거라와 들어있는 거리를 비교해서 수를 세는 것이였는데바로 망했다 ㅎㅎ 7퍼에서 틀린다. 생각해보니 예외가있따 ㅎㅎ 문제를 푸는 방법을 봤따 ㅎㅎ푸는 방법은1. 각 정점에서 루트까지 거리와 가장 가까운 리프까지 거리를 구한다2. 모든 정점을 돌아보며 3. 루트가 아니고 && 리프까지 거리..

정점과 간선이 n,m(

교차하는 케이블의 수를 세는 문제다펜윅트리 or 머지소트로 풀수있다..!처음에 세그먼트트리로 풀었는데 계속 시간초과가 나길래방법이 틀린 줄 알았는데 map을 써서 시간초과가 났따 ㅎㅎ 문제를 푸는 방법은 1. 펜윅트리를 만든다. 초기값은 모두 02. 1~n까지 탐색을하며 B에서의 나의 위치 뒤에있는 것의 합을 더한다!3. 그리고 나의 위치를 트리에서 1로 바꿔준다 교차점의 수를 세는 것이므로 A의 앞에있던 공장이 B에서는 뒤에있다면 교차점이 생긴다. 그래서 뒤에 1이 몇개있는지만 세어주면 된다! 소스코드 - 펜윅트리12345678910111213141516171819202122232425262728293031323334353637383940#include #include #include using nam..

3개의 증가수열을 고르고 그 때의 비용이 최소를 찾는 문제다N^2 DP로 풀었다 d[pos][cnt]로 테이블을 잡고 pos까지 봤고 cnt개 더 고를 수있을 때로 문제를 풀었다 문제 풀고 틀려서 보니 메모이제이션을 안했다 ㅎㅎ소스 잘 봐야겠따..! 소스코드1234567891011121314151617181920212223242526272829303132333435363738394041424344#include #include #include #include #include #include #include #include #include #include #define ll long long#define inf 1e17using namespace std;ll arr[3030], cost[3030];int ..

dfs순서로 방문한다는 점을 이용해서 답을 찾으면 된다 나는 set충이므로 set을 사용했다..! 1. set에 방문한 정점을 담는다2. 새로운 정점을 방문했다면 그 이전 정점이 부모다(부모에서 자식으로 가므로)3. 이미 방문한 정점이면 건너뛴다4. set의 크기 == 정점 수 소스코드12345678910111213141516171819202122#include #include #include using namespace std;int n;int arr[200020], ans[200020];sets; int main() { scanf(" %d", &n); for (int i = 0; i

r,f 좌표를 통해 고객이 어디에 해당하는지 분류하는 문제다.r은 현재시간 - 가장 최근 접속시간f는 유저의 접속 횟수다 맵을 이용해서 를 저장하면 문제를 풀 수있다! 근데 소스가 더럽다!처음에 틀렸는데 다음 코드를 추가하니 맞았다.cin이 느려서 그런가보다 ios::sync_with_stdio(false); cin.tie(0); 소스코드1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677#include #include #include #include #include using namespace st..

3개의 점이 직선인지 아닌지 판단하는 문제다CCW를 이용하면 쉽게 판단할 수 있다CCW를 사용해서 직선이면 0을 리턴하므로 0인지 아닌지만 확인하자! 소스코드1234567891011121314#include using namespace std;int ccw(int x1, int y1, int x2, int y2, int x3, int y3) { int ret = x1*y2 + x2*y3 + x3*y1; ret -= (y1*x2 + y2*x3 + y3*x1); return ret;} int main() { int x1, y1, x2, y2, x3, y3; cin >> x1 >> y1 >> x2 >> y2 >> x3 >> y3; if (ccw(x1, y1, x2, y2, x3, y3)==0) puts("WH..

문제 제목부터 디스크립션까지 너무 좋은 문제다 문제는 SCC의 기본문제이다dfs로 풀면 cycle때문에 풀수가없다! 문제를 푸는방법은1. SCC를 통해 cycle이 없는 그래프로 만든다2. 각각의 컴포넌트의 indegree를 계산한다3. indegree가 0인 곳에만 바이러스를 넣어야 최소이다!! 소스코드12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182#include #include #include #include #include using namespace std;int n, ..

(301,301) 까지 가면서 다 보면 된다처음에 d[300][300][600] 해서 시간까지 테이블로 잡으려다가 메모리 보고 포기했다 ㅎㅎ 시간을 잡지않아도 (0,0)에서 위,오른쪽만 움직이기 때문에시간 = x+y가 된다. 따라서 m-x+y가 현재위치에서의 사탕 수 이다 소스코드123456789101112131415161718192021222324252627#include #include #include using namespace std;int d[303][303];bool arr[303][303];int n, m; int go(int x, int y) { if (x >= 301 || y >= 301) return 0; int&ret = d[x][y]; if (ret != -1) return ret;..