Dev.baelanche

투포인터를 통해 hi * hi - low * low 와 G를 비교한다. 투포인터 탐색을 언제 멈출건지가 가장 중요한데, low + 1 = hi 이고 두수의 제곱의 차가 G보다 작으면 더이상 연산할 필요가 없다. 또한 현재 몸무게와 이전 몸무게는 모두 자연수로 0이 될 수 없다는 점을 주의하자. public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int g = sc.nextInt(); int lo = 1; int hi = 1; boolean f = false; while(true) { long minus = (long)(Math.pow(hi, 2)) - (long)(Math.pow(l..

배열의 부분합을 투포인터 기법으로 찾아낸다. 투포인터가 언제나 최소길이의 합을 사용하므로 sum >= s 만 비교해주면 된다. 최초에 초기화한 최소 길이에 변화가 없다면 0을 출력해준다. public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int s = sc.nextInt(); int a[] = new int[n]; for(int i=0; i= s) { sum -= a[lo++]; min = Math.min(min, hi-lo+1); } else if(hi == n) break; else sum += a[hi++]; } System.out.pr..

소수리스트를 만들어 놓고 투포인터 기법으로 수열의 합과 N을 비교한다. 투포인터 기법 자체가 연속된 배열을 사용하므로 문제에서 요구하는대로 풀 수 있다. public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); boolean prime[] = new boolean[n+1]; for(int i=2; i

부분합배열을 만들어도 O(n^2) 으로 시간초과가 난다. 임의의 변수 start, end를 만들어서 start ~ end 의 합과 m을 비교하며 두 변수의 값을 조정하는 방식으로 풀었다. 이 방법을 투 포인터라고 한다. 1. start ~ end의 합 sum을 m과 비교한다. 1-1. sum >= m 일때 합을 줄여아하므로 start값을 올려주고 그 값만큼 sum에서 빼준다. 1-2. end가 n일때 배열을 초과하였으므로 정지한다. 1-3. sum < m 일때 합에 수를 더 더해야하므로 end값을 올려주고 그 값만큼 sum에 더한다. 1-4. sum == m 일때 카운트 한다. public class Main { public static void main(String[] args) { Scanner sc..