본문 바로가기

problem solving

 (93)
1182번: 부분수열의 합 문제를 풀다보면 사고력이 많이 부족하단 걸 느낀다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 #include #include void DFS(std::vector val, int len, int cur, int sum, int result, int *count) { if (cur == len) { if (sum == result) { *count += 1; } return; } DFS(val, len, cur + 1, sum + val[cur], result, count); DFS(val, len, cur + 1, sum, result, count); } int main(vo..
1168번: 요세푸스 문제2 혼자 힘으로 풀지 못했다. 퍼포먼스를 만족키지 못했는데 다른 사람들의 풀이를 참조해서 vector의 erase를 사용하면 된다는 걸 알았다. (erase는 memmove로 구현해서 매우, 매우 빠르다고 한다) 하지만 이 문제는 세그먼트 트리를 사용하라는 목적으로 만든 것 같다. 세그먼트 트리를 알아보자... #include #include int main(void) { int len, term; std::cin >> len >> term; std::vector arr(len); for (int i = 0; i
1167번: 트리의 지름 시작점을 어디로 잡아도 상관없다. 선택한 시작점에서 가장 깊은 곳을 찾아낸 후 그곳에서 최대 지름을 구한다. (처음 주어진 시작점이 가장 깊은 곳이 아닐수도 있다는 것에 숙지하고 있어야한다) #include #include #include #include #include std::vector val[100001]; bool check[100001] = { false }; int max = 0, final = 0; void BFS(int pos) { std::queue mQueue; mQueue.push({ pos, 0 }); check[pos] = true; while (!mQueue.empty()) { int front = mQueue.front().first; int count = mQueue.fro..
1149번: RGB거리 가장 익숙해지지 않는 dp문제 #include #include int main(void) { int len; std::cin >> len; int val[1001][3] = { 0 }; for (int i = 0; i val[i][j]; } } int store[3] = { 0 }; int red, green, blue; red = val[0][0]; green = val[0][1]; blue = val[0][2]; for (int i = 1; i store[2] ? store[2] : store[1]; val[i][1] += store[0] > store[2] ? store[2] : store[0]; val[i][2] += store[0] > store[1] ? store[1] : store[0]; }..
1021번: 회전하는 큐 데크를 이용해 간단하게 풀 수 있다. #include #include #include #include int main(void) { int len, N; std::cin >> len >> N; std::vector val(N); for (int i = 0; i > val[i]; } std::deque mDeque; for (int i = 0; i cur) { int pos; for (int i = 0; i len / 2) { //뒤로 밀기 while (mDeque.front() != val[cur]) { int back = mDeque.back(); mDeque.pop_back(); mDeque.push_front(back); count++; } mDeque.pop_front(); len--; cur++..

티스토리툴바