Dev.baelanche

배열의 부분합을 투포인터 기법으로 찾아낸다. 투포인터가 언제나 최소길이의 합을 사용하므로 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

신나는 완전탐색 문제다. 방문배열을 백트래킹 하며 진행했다. public class Main { static int n; static boolean visited[]; public static void main(String[] args) { Scanner sc = new Scanner(System.in); n = sc.nextInt(); visited = new boolean[n+1]; dfs(0, ""); } public static void dfs(int cnt, String s) { if(cnt == n) { System.out.println(s); return; } for(int i=1; i

DP문제 RGB거리와 상당히 유사한 문제이다. 배열의 n-1번째부터 0번째까지 반대 방향으로 진행하면서 최고합, 최소합을 메모이제이션 하면서 구하면된다. n이 최대 100000이라 DP로 그냥 풀리긴 하지만 메모리 제한을 보니 슬라이딩윈도우 기법을 요구하는 듯하다. 슬라이딩 윈도우는 일정한 구간을 훑으며 진행하는 기법이다. 글로 표현하면 뭔가 있어 보이는데, 배열 크기를 1로 만들어서 이전 배열에서 연산한것을 갱신만 해주면 된다. colMax, colMin 은 최대합, 최소합 배열이고 tempMax, tempMin 은 이전계단의 값이다. colMax, colMin 배열에 tempMax, tempMin의 값을 연산을 통해 업데이트 시켜주면 된다. public class Main { public static..

부분합배열을 만들어도 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..

최근 한달동안 푼 문제중 가장 어려웠다;;; 1. 10^7 의 제곱은 10^14 이므로 10^7 보다 큰 수들은 소수 여부를 판별하지 않아도 된다. int max = 10000000; boolean prime[] = new boolean[max+1]; 2. 2부터 B보다 작거나 같은 거의 소수들을 리스트에 담는다. ArrayList list = new ArrayList(); for(int i=2; i

n보다 작거나 같은 소수에 대해 문제의 로직을 통해 소수상근수를 구해야 한다. 2는 상근수가 아님을 알려주어서 3부터 n까지의 소수상근수 계산을 수행했다. 상근수가 아님을 알기위해 상근수 계산을 하며 구한값들을 집합에 담아 중복체크를 했다. public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); boolean prime[] = new boolean[1000001]; for(int i=2; i

일단 소수배열을 구한다. 임의의 수 x 에 대하여 x, n-x 가 모두 소수일때 문제의 조건을 만족한다. public class Main { public static void main(String[] args) throws Exception { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); boolean prime[] = new boolean[1000001]; for(int i=2; i