교차하는 케이블의 수를 세는 문제다펜윅트리 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