Dev.baelanche

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

에라토스테네스의 체 방법으로 소수 배열을 구해놓고 합성수 k 에 대해 k보다 크면서 가장 가까운 소수 - k보다 작으면서 가장 가까운 소수를 구한다. public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); boolean prime[] = new boolean[1299710]; for(int i=2; i2 && i*j0) { int k = sc.nextInt(); if(prime[k]) { int s = k; int e = k; while(true) { if(!prime[--s]) break; } while(true) { if(!prime[++e]) break; } System.out.p..

BFS로 치즈의 외곽을 구하고 반복된 시뮬레이션으로 정답을 도출했다. 1. 주어진 n, m을 n+2, m+2 하여 배열을 만든다. 치즈 외곽 탐색을 위해 편의상 바깥쪽 배열을 한칸씩 여유를 두었다. 2. 배열 탐색을 줄이기 위해 치즈의 개수를 세어 변수에 담는다. 3. 치즈가 녹기 전의 배열을 저장한다. 4. 외곽 치즈를 체크한다. (0, 0)은 무조건 치즈가 없으므로 BFS를 통해 치즈가 없는 부분을 모두 체크한다. (배열 값을 -1로 만들었다.) 5. 치즈 배열 인덱스에서 상하좌우 중 한개라도 -1이면 외곽의 치즈이므로 임의의 큐에 담는다. 6. 큐에 담은 좌표를 모두 0으로 바꾼다. 7. -1로 만든 외곽치즈를 다시 0으로 바꾼다. public class Main { static int n; sta..

처음에는 DFS + 완전탐색으로 풀었는데 당연히 시간초과가 났다. 틀린소스 (타임아웃) public class Main { static int n; static int m; static int a[][]; static int dx[] = {0, 1}; static int dy[] = {1, 0}; static int max = 0; public static void main(String[] args) throws Exception { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st; st = new StringTokenizer(br.readLine()); n = Integer.parseI..