본문 바로가기

Two Pointers2

[BOJ 2143] 두 배열의 합 https://www.acmicpc.net/problem/2143 2143번: 두 배열의 합 첫째 줄에 T(-1,000,000,000 ≤ T ≤ 1,000,000,000)가 주어진다. 다음 줄에는 n(1 ≤ n ≤ 1,000)이 주어지고, 그 다음 줄에 n개의 정수로 A[1], …, A[n]이 주어진다. 다음 줄에는 m(1≤m≤1,000)이 주어지고, 그 다음 줄에 m개의 정수로 B[1], …, B[m]이 주어진다. 각각의 배열 원소는 절댓값이 1,000,000을 넘지 않는 정수이다. www.acmicpc.net n과 m의 값이 크지 않기 때문에 각 배열의 합을 구하는 것은 가능하다. 이를 이용하여 A배열과 B배열의 연속합을 저장해둔 배열을 만들고, 이를 정렬한 뒤 각 합을 따로 합쳐보면서 개수를 세면 .. 2020. 4. 20.
[BOJ 1806] 부분합 https://www.acmicpc.net/problem/1806 1806번: 부분합 문제 10,000 이하의 자연수로 이루어진 길이 N짜리 수열이 주어진다. 이 수열에서 연속된 수들의 부분합 중에 그 합이 S 이상이 되는 것 중, 가장 짧은 것의 길이를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 N (10 ≤ N < 100,000)과 S (0 < S ≤ 100,000,000)가 주어진다. 둘째 줄에는 수열이 주어진다. 수열의 각 원소는 공백으로 구분되어져 있으며, 10,000이하의 자연수이다. 출력 첫째 줄에 구하고자 하는 최소의 길 www.acmicpc.net 위 문제를 전체 탐색을 하면 O(N^2)으로 N이 100000이어서 시간초과가 난다. 투 포인터 알고리즘을 이용하여 풀 수 있다. 배열에 .. 2020. 4. 17.

티스토리툴바