https://www.acmicpc.net/problem/2473전에 풀었던 두 용액을 섞어서 0과 가장 가까이 만드는 문제와 세 수를 합해서 딱 0을 만드는 문제를 합친 버전이다. 우선 0과 가장 가까이 만들어야하고, 세 수를 합한다는 점에서 (i, j)의 합을 먼저 구하고 그 합과 어떤 숫자 idx를 합해서 0과 가장 가까이 만드는 idx를 찾는 방식으로 접근했다. 문제는 두 용액이 아닌 세 용액이라는 점이다. 기존 두 용액에서는 lower_bound(~~, ~~, -i) = idx 라 했을 때 idx - 1, idx를 보면 된다. 다만 idx가 i와 겹치는 경우를 고려해서 idx + 1까지 봤던 것이었다.이번에는 용액이 세 가지이므로 idx는 idx + 1을 똑같이 보고, [i, j] 와 같은 경우..

https://www.acmicpc.net/problem/2467https://www.acmicpc.net/problem/3151용액을 먼저 풀어보고 합이 0을 풀어보는 것을 추천한다. 백준 2467: 용액용액은 간단하게 합이 0과 가장 가까운 index를 찾으면 된다.arr [i]를 기준으로 찾으면 될 것 같은데 결론부터 말하자면 arr [i]와 합이 0과 가장 가까워지는 index를 찾으려면 -arr [i]를 lower_bound() 함수에 적용하면 된다. lower_bound(~~, ~~, -arr [i])의 결과는 -arr [i] 이상인 값이 될 테고 그 값을 arr [k]라 하자.arr [k]는 -arr [i]가 될 수도 있고 그 값보다 클 수도 있다. 또, arr [k-1]은 -arr [i] ..

https://www.acmicpc.net/problem/5904N이 10^9 개로 N번째 글자를 구한다는 것이 몇 번째 수열을 구해야 하는지 감도 안잡히고 굉장히 큰 수여서 long long으로도 담지 못한다.즉, 재귀적으로 길이가 n 이상인 수열을 구해서 n번째 문자를  찾으려 한다면 절대 풀 수 없다.조금 다르게 생각해서 n번째 글자만 알면 되므로 어떤 수열에 대해 n번째 글자를 알아내는 과정을 재귀로 생각하여야 한다. 사실 다 풀고 나서야 이렇게 명료하게 말할 수 있지만 풀 때는 다음과 같은 과정을 거쳤다.수열의 길이가 n 이상인 moo 수열 구하기 -> 구현을 다 하고 보니 n이 얼마 이상 커지면 오류k번째 moo 수열 S(k)에 대해 S(k-1)의 길이를 알면 S(k)를 알 수 있음. 그럼 길..

https://www.acmicpc.net/problem/1647예제7 121 2 31 3 23 2 12 5 23 4 47 3 65 1 51 6 26 4 16 5 34 5 36 7 4ans : 8문제의 요구사항은 다음과 같다.도시를 2개로 분할하라.분할된 2개의 도시 사이에는 간선이 존재하지 않는다.각 도시의 마을은 MST로 구성되어 있다.일단 3번 조건을 보면 MST를 구현해야하긴 하는데 어떻게 2개로 분할해야 가장 Minimum한 MST를 만들 수 있을지가 고민된다.N이 100개정도면 완전탐색으로 구현해도 될테지만 N은 10만... 완전탐색은 아니다. 만약 도시 분할 조건이 없다면 바로 MST를 구해도 된다. 그렇다면 MST를 구하는 과정에 Union-Find를 하게 되고 이 부분을 응용해서 2개의 ..

예제454430 2 2 22 0 3 32 3 0 42 3 4 0출력 : 9MST 문제인데 MST 문제는 구현도 어렵지만 왜 MST인지 잘 판단해야 한다. 논을 파는 방법은 직접 논에 우물을 파거나 다른 논에서 끌어오는 방법이 있다.당장 떠오르는 방법은 그리디 하게 가장 싼 우물을 파되, 불필요하게 사이클이 생겨서는 안 되고 최소한의 개수만큼 파야 한다. 사이클이 생겨서는 안 되고 최소한의 개수만큼 파야한다는 점에서 MST를 떠올렸고 프림 알고리즘을 선택했다. 알고리즘은 다음과 같다.우물을 파는 비용을 모두 우선순위 큐에 넣는다.우선순위 큐에서 논을 하나 빼서 MST에 포함시킨다.MST에 포함된 논의 간선 중 MST가 아닌 논과 연결된 간선을 우선순위 큐에 넣는다.N개의 논에 대해 N-1개의 간선이 MST..

https://www.acmicpc.net/problem/2637 예제785 1 25 2 27 5 26 5 26 3 36 4 47 6 37 4 5출력 : 1 162 163 94 17하나의 완제품을 완성하는데 필요한 기본 부품의 수를 구하는 문제이다. 어떤 부품이 기본 부품인지를 구하고, 중간 부품을 기본 부품으로 치환하는 방식으로 풀이를 떠올렸다. dp를 사용한 방식인데 2차원 배열로 dp 배열을 선언해서 dp [i][j]를 i번 부품을 만드는데 필요한 j 부품의 수 (j는 기본 부품)로 생각하고 구현했다. 해당 풀이의 점화식은 다음과 같다.i번 부품에 대해(i는 중간 부품) dp[i] = dp [next.first] * next.second. next는 i번 부품을 만드는데 필요한 부품이다. 백준에서 ..