문제https://www.acmicpc.net/problem/1806 접근 방법N개의 수열에서 부분합 중 합이 S가 되는것을 구하는 문제이다.완탐으로 푼다면 10만 *10만 시간초과가 발생할 것이다.따라서 투포인터로 풀 수 있었다.코드import java.io.BufferedReader;import java.io.InputStreamReader;import java.util.StringTokenizer;public class Main { private static StringBuilder sb; private static BufferedReader br; private static StringTokenizer st; private static int N,S; private st..

문제https://www.acmicpc.net/problem/15831 접근 방법준표는 까만색을 싫어하고 , 흰색 돌은 좋아한다. 최대가 B까지 정해져있고, 최소 W만큼 조약돌을 주어야 한다.브루트포스로 가능하지만 N값이 30만으로 O(N^2) 시간초과가 발생한다.따라서 투포인터를 생각하였고, 포인터를 넘어가며 B 조약돌이 최대를 넘으면 최대경계선 까지 포인터를 옮겨주어야 한다.(코드를 보는것이 이해가 더 빠를 것이다.) 코드import java.io.BufferedReader;import java.io.InputStreamReader;import java.util.StringTokenizer;public class Main { private static StringBuilder sb; pri..

문제https://www.acmicpc.net/problem/16472 접근 방법문자열에서 인식할 수 있는 알파벳 종류가 N일때 N개의 언어로 이루어진 수열의 최고 길이를 구하는 문제이다.이 문제는 브루트포스로 구할 수 있지만 시간 초과가 발생한다. O(N^2) 10만 *10만 = 100억따라서 반복문 하나를 줄일 수 있는 방법인 투 포인터를 생각하였다.코드를 보는 것이 조금 더 이해가 쉬울 것이다.접근 방법import java.io.BufferedReader;import java.io.InputStreamReader;import java.util.StringTokenizer;public class Main { private static StringBuilder sb; private stati..

문제https://www.acmicpc.net/problem/14465 접근 방법정상적으로 작동하는 연속 K의 신호등이 존재하려면 최소 몇개의 신호등을 수리해야하는지 구하는 문제이다.브루트포스로도 가능하지만 시간초과가 발생한다.따라서 투포인터로 시간을 줄일 수 있다.연속하는 구간이 고정되어 있으므로 슬라이딩 윈도우 기법을 사용한다.코드import java.io.BufferedReader;import java.io.InputStreamReader;import java.util.StringTokenizer;public class Main { private static StringBuilder sb; private static BufferedReader br; private static Str..

문제https://www.acmicpc.net/problem/1644 접근 방법N을 연속된 소수의 합으로 몇가지 방법이 있는지를 구하는 문제이다.따라서 소수를 에라토스테네스의체로 list에 넣어두었다.또한 연속된 수의 합은 사실 브루트포스로 가능하지만 시간초과가 발생하는것을 방지하기 위해 투포인터로 구했다.소수를 리스트에 넣어놨기 때문에 N이 400만일걸 예상하여 list.get(s)+list.get(e) 코드import java.io.BufferedReader;import java.io.InputStreamReader;import java.util.ArrayList;import java.util.Arrays;import java.util.StringTokenizer;public class Main { ..

문제https://www.acmicpc.net/problem/22862 접근 방법수열 에서 최대 K번 숫자를 지워서 제일 긴 짝수 수열을 만드는 문제이다.부르트포스로 셀 수 있지만 시간초과가 발생한다고 생각했다.따라서 투 포인터로 문제를 푸는 방식을 생각했다.포인터 S를 0 포인터 E를 0으로 두고 E를 경계선이라 생각하며 최대값을 교환해 주었다.코드import java.io.BufferedReader;import java.io.InputStreamReader;import java.util.StringTokenizer;public class Main { private static StringBuilder sb; private static BufferedReader br; private s..

문제https://www.acmicpc.net/problem/2467 접근 방법음수인 알칼리 용액과 양수인 산성 용액을 더해서 0이랑 최대한 가까이 만드는 것이 문제다.따라서 브루트포스로 문제를 푼다면 N값이 10만이므로 시간초과가 발생할것을 생각했다.그래서 이 문제를 투포인터로 풀면 된다고 생각했다.코드import java.io.BufferedReader;import java.io.InputStreamReader;import java.util.StringTokenizer;public class Main { private static StringBuilder sb; private static BufferedReader br; private static StringTokenizer st; ..

문제https://www.acmicpc.net/problem/1484 접근 방법브루트포스로 풀 수 있지만 그랬을 경우 O(N^2)으로 시간 초과가 발생한다.따라서 반복문을 줄일 수 있는 방법으로 투포인터를 생각했다.그리고 문제는 살이 찐 경우만 체크하면 된다. (값이 자연수이다.)따라서 포인터를 두고 앞에서부터 탐색하는 방법으로 문제를 풀었다.코드import java.io.BufferedReader;import java.io.InputStreamReader;import java.util.StringTokenizer;public class Main { private static StringBuilder sb; private static BufferedReader br; private sta..

문제https://www.acmicpc.net/problem/3273 접근 방법a1+ a2가 X를 만족하는 수를 구하는 문제이다.브루트포스로 구하면 시간초과 O(N^2)가 발생하므로 반복문을 줄일 수 있는 투포인터를 이용하여 문제를 푼다. 코드import java.io.BufferedReader;import java.io.InputStreamReader;import java.util.Arrays;import java.util.StringTokenizer;public class Main { private static StringBuilder sb; private static BufferedReader br; private static StringTokenizer st; private ..

문제https://www.acmicpc.net/problem/2003 접근 방법만약 완전탐색으로 구할 경우 O(N^2) 시간 초과가 발생한다.따라서 N^2을 O(N) 으로 줄일 수 있는 투 포인터를 생각하여 문제를 구했다.s, e 둘다 0으로 시작하고, 값이 작으면 e를 증가, 값을 초과하면 s를 증가시켰다. 코드를 보는것이 더 이해하기 쉬울 것이다.코드import java.io.BufferedReader;import java.io.InputStreamReader;import java.util.StringTokenizer;public class Main { private static StringBuilder sb; private static BufferedReader br; private..