벨로그로 바꿀까 고민하는 블로그

https://www.acmicpc.net/problem/2632 2632번: 피자판매 첫 번째 줄에는 손님이 구매하고자 하는 피자크기를 나타내는 2,000,000 이하의 자연수가 주어진다. 두 번째 줄에는 A, B 피자의 피자조각의 개수를 나타내 는 정수 m, n 이 차례로 주어진다 (3 ≤ m, n www.acmicpc.net 누적합을 구하는 방법을 잘 모르겠어서 그 부분만 풀이를 참고하고, 누적합 벡터를 구하고 나서 정렬한 후, 두 포인터 알고리즘을 이용해서 풀었다. A피자 또는 B피자만 선택하는 경우를 고려하지 않아서 좀 오래걸렸다ㅠㅠ HTML 삽입 미리보기할 수 없는 소스 참고 2632번 풀이: https://blogshine.tistory.com/588

https://www.acmicpc.net/problem/7453 7453번: 합이 0인 네 정수 첫째 줄에 배열의 크기 n (1 ≤ n ≤ 4000)이 주어진다. 다음 n개 줄에는 A, B, C, D에 포함되는 정수가 공백으로 구분되어져서 주어진다. 배열에 들어있는 정수의 절댓값은 최대 228이다. www.acmicpc.net 당연한거지만 모든 순서쌍 조합을 for문으로 만들려고 하면 시간복잡도가 O(n^4)가 되기 때문에 최대 4000 ^ 4번 연산을 해야하므로 시간 초과가 발생할 것이 뻔하다... 두 포인터 알고리즘을 사용하면 O(n^2)으로 줄일 수 있따. 풀이) A, B, C, D 리스트를 입력받는다. 가능한 A[a], B[b]의 합을 모두 구해 AB 리스트에 저장하고, AB 리스트를 정렬한다...