여니손

문제 링크 : https://www.acmicpc.net/problem/12100🍊해결방법배열에 5가지의 방향이 나올 수 있는 경우의 수 저장tmp배열에 arr배열을 복사하여 5가지 방향으로 실행각 방향에 따라 movingPoint 실행하여 tmp 배열에 결과 값 저장한번 dir 방향으로 움직일 때 한번 합쳐진 곳은 해당과정에서 다시 합쳐지면 안되기에 visit을 통해 방문처리move 끝나고 max 값 갱신😀풀이import java.io.*;import java.util.*;public class Main { static int N; static int[][] arr; static int[] dirArr; static int[][] tmp; static int max; ..

문제 링크 : https://www.acmicpc.net/problem/2637🍊해결방법하나의 부품을 만들기 위해서 이전의 부품이 필요함위상정렬 활용기본부품은 1 2 3 4가 아니라 이전 부품이 없는 부품들이다!!!! - 이거 때문에 애 먹었다 ㅎㅎㅎㅎ😀풀이import java.io.*;import java.util.*;public class Main { static class Node{ int x, cnt; Node(int x, int cnt){ this.x = x; this.cnt = cnt; } } static int N; static int M; static int[] in; stati..

문제 링크 : https://www.acmicpc.net/problem/1450🍊해결방법냅색문제라서 dp를 활용하려 했지만 2차원 배열에서 각각 최대 10억이라 메모리초과...모든 경우의 수를 따져보려 했지만 2^30이라 시간초과두 그룹으로 나눠서 합이 나올 수 있는 경우의 수를 각각의 리스트에 저장한개의 리스트만 정렬하여 이진탐색에 활용list1에 있는 모든 경우를 보면서 list2에서 이진탐색을 활용C이하의 무게를 만족하는 가장 큰 idx를 찾아 cnt 플러스😀풀이import java.io.*;import java.util.*;public class Main { static int[] arr; public static void main(String[] args) throws IOExce..

문제 링크 : https://www.acmicpc.net/problem/2295🍊해결방법세수의 합을 구하고 나서 그 합을 이진탐색으로 찾으려고 하면 N^3 을 시간초과두수의 합을 미리 구하자sum + arr[i] = arr[j] 이 조건을 만족하면 됨sum = arr[j] - arr[i] 이중 for문을 사용해서 조건을 구하고 sum을 이진탐색 돌면서 확인하자N^2으로 해결😀풀이import java.io.*;import java.util.*;public class Main { static int N; static int[] arr; static int max; public static void main(String[] args) throws IOException { ..

문제 링크 : https://www.acmicpc.net/problem/2252🍊해결방법그래프에서 관계가 주어졌기에 위상정렬을 이용해보자in 배열을 사용하여 자기 자신보다 앞에서야 하는 숫자의 개수를 체크하자in 배열에 값이 0이라는 건 나보다 앞에 없으므로 Queue에 넣어서 그 다음을 확인Queue에서 나왔다는 것은 줄을 선 것이므로 해당 num과 관련된 in[idx]-- 로 제거하자😀풀이import java.io.*;import java.util.*;public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputS..

문제 링크 : https://www.acmicpc.net/problem/2616🍊해결방법i번째에서 M개까지 기차를 끌고 간다 -> 다음으로는 i+M번째로i번째에서 선택을 하지 않는다train(idx+M, cnt+1) / train(idx+1, cnt) 두 경우의 수 중 최대값을 return 한다최대값을 계산할 때 누적합을 활용하자 prefix[idx+M-1] - prefix[idx-1]중복된 계산을 할 수 있으므로 dp에 저장하자😀풀이import java.io.*;import java.util.*;public class Main { static int N; static int[] arr; static int[] prefix; static int M; static int[][..

문제 링크 : https://www.acmicpc.net/problem/1208🍊해결방법모든 경우의 수를 확인하기에는 2^40으로 시간초과어차피 부분수열의 합을 찾는거기에 두 그룹으로 나누어서 합끼리 찾아보자두 그룹의 부분수열로 만들 수 있는 합을 각각의 List에 저장두개의 List에 M이 있는지 먼저 체크하나의 List를 정렬하여 이진탐색으로 합이 M이 되는걸 찾아보자이진탐색할 때 같은 값이 여러개 있을 수 있으니 lowerBound와 upperBound를 활용해서 구간을 찾자부분집합의 크기가 1이상인거를 조심하고, lowerBound와 upperBound 중 하나라도 못 M인 경우의 수 못 찾으면 스킵😀풀이import java.io.*;import java.util.*;public class M..

문제 링크 : https://www.acmicpc.net/problem/17069🍊해결방법N이 최대 32이므로 최악의 경우 3의 32*32 제곱이 일어나므로 일반 구현으로는 시간초과dp를 활용하여 해당 좌표의 경우의 수를 탐색 완료했으며 저장가로, 세로, 대각선일 때 이동하는 방향 다름대각선일 때 특이하게 색칠된 부분이 빈 공간이어야 이동가능!!😀풀이import java.io.*;import java.util.*;public class Main { static int N; static int[][] arr; // 가로 세로 대각 static int[] dx = {0, +1, +1}; static int[] dy = {+1, 0, +1}; static long[][][]..

문제 링크 : https://www.acmicpc.net/problem/14567🍊해결방법선수과목이라는 특정 조건이 존재선수과목을 리스트를 통해서 저장하자과목 배열을 만들어서 해당 과목이 몇 학기 만에 끝나는지 저장하자처음에는 과목 배열 모두 1로 초기화 (선수과목이 없는 과목도 있기 때문에)1 ~ N 개의 과목을 다 보면서 해당 선수과목이 있는지 확인하고 있으면 +1 해서 최대값 갱신dp[num] = Math.max(dp[num], dp[i]+1)최대값을 저장해야하는 이유는 같은 선수과목이 존재하게 되면 젤 오래 걸리는 과목이 끝나고서 해당 과목이 끝나는 거 이므로 최대값을 저장해야 한다😀풀이import java.io.*;import java.util.*;public class Main { s..

문제 링크 : https://www.acmicpc.net/problem/2482🍊해결방법처음에 visit 배열을 사용해서 한칸씩 움직이면서인접한 색을 판단하려 했는데 이럴경우 잘못된 경우인데 메모이제이션을 불러와서 오답예를들어 N=6 이고 3가지의 색상을 뽑는 과정에서1번, 3번을 색칠하고 dp[5][2]에 1이 저장된다. 그러나 1번과 4번을 색칠하고 나서 더이상 색칠할 수 없는데dp[5][2]가 return이 되어 경우의 수로 판단그럼 visit 배열로 하지말고 현재 선택하면 다음다음 걸 선택하면 되니깐 idx+2로 생각해서 접근현재의 idx를 선택하는 경우 와 현재의 idx를 선택하지 않는 경우 이렇게 2가지가 나온다idx > N 또는 남아있는 후보 개수가 칠할 수 있는 개수보다 작다면 경우의 수..