Jonyo Programming

[BOJ 7453(G2)리뷰] 이전에 풀었던 BOJ : 2143 두 배열의 합 문제와 비슷한 유형의 문제다. 다만 배열의 개수가 2개에서 4개가 되었고, 이번엔 4개의 배열의 합이 0인 쌍들의 개수를 구해야 한다. 과정은 지난 문제와 비슷하다. 다만 조금 로직을 다르게 했다. 일단 먼저 A,B,C,D배열을 AB배열의 두 배열의 합으로 합치고, CD배열의 두 배열의 합으로 합쳤다. 그리고 마찬가지로 오름차순으로 정렬을 해줬다. 이제 이 두 배열에는 A,B배열을 서로 더한값과 B,C배열을 서로 더한값이 오름차순으로 정렬되어 있다. 처음엔 이 상태에서 투 포인터를 이용해 풀었지만 시간초과를 맞았다. map에 갯수를 세는 과정에서 발생한것이라 생각된다. 그래서 이번엔 합이 0인 쌍들을 구한다는 특성을 이용하여 ..

[BOJ 2143(G3)리뷰] 투 포인터를 응용해야 하는 문제이다. 문제에서 배열이 두개가 주어지고, 두개의 배열을 이용하여 만들 수 있는 합 중 T를 만족하는 경우의 수를 찾아야 한다. 완전탐색하는 방법으로는 시간초과를 맞게 되므로 투포인터 알고리즘을 이용해야 한다. 투 포인터 알고리즘을 이용하기 위하여 A와 B배열에 대해 각각의 구간합을 저장하는 사전작업을 했다. 즉, 1,3,2,1 배열이라면 1 4 6 7 3 5 6 2 3 1 라는 별도의 배열을 만든다. 그리고 이렇게 만들어진 두개의 배열을 각각 오름차순으로 정렬 한 후에 하나의 배열은 시작부터, 하나의 배열을 끝부터 시작한다. 이미 이 배열에 구간의 합에 대한 경우의 수가 들어 있으니 이 두개의 배열의 합이 T를 만족하는 개수를 찾으면 된다. 다..