은비블로그

https://www.acmicpc.net/problem/2240 [풀이과정]3차원 DP로 풀었다.for( 1 -> T ){ for( 1 -> W+1 ){ 매초마다 해당 시간에 떨어지는 열매 1. 1번 나무로 떨어질 때 1-1. 해당 위치로 이동해서 1-2. 그대로 2. 2번 나무로 떨어질 때 2-1. 해당 위치로 이동해서 2-2. 그대로 }}  *W+2로 초기화한 이유는 w = W+1일 때, W번 이동했을 경우를 계산할 수 있기 때문이다. [코드]import java.io.*;import java.util.StringTokenizer;/*매 초마다 두 개의 나무 중 하나의 나무에서 자두가..

https://www.acmicpc.net/problem/17404 [풀이과정]최대한 단순하게 생각하는 것이 풀이의 핵심인 것 같다.RGB거리 실버 1보단 어려웠다.https://www.acmicpc.net/problem/1149 [코드]import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.StringTokenizer;/*집이 N개.각각의 집을 빨강, 초록, 파랑으로 칠하는 비용이 주어졌을 때,1. 1번 집의 색은 2번, N번 집의 색과 같지 않아야 한다.2. N번 집의 색은 N-1번, 1번 집의 색과 같지 않아야 한다.3. i(2

https://www.acmicpc.net/problem/12865 [풀이방식]Top-down 방식으로 풀었다.DP[n][k]: n번째 물건까지 고려했을 때, 배낭의 용량이 k일 때 얻을 수 있는 최대 가치. [코드]import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.StringTokenizer;/*N개의 물건. 각 무게 W, 가치 VK만큼의 무게에서 최대 가치 구하기 */public class Main { static BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); sta..

다른 분들의 풀이를 봐도 감도 못 잡다가, 그냥 해보니까 됐다(?) 처음에 또 최소경우 고려 안 해서 런타임에러 뜸 배열을 [2][N+1]로 바꾼 후 맞았다 가장 긴 증가하는 부분수열에서처럼 DP를 해당 인덱스까지의 합으로 두고 풀었음. 내가 푼 건 맞는데 뭔가 찝찝.. 머리로 푼 게 아니라 몸으로 푼 느낌.. DP문제를 더 풀어봐야겠다 1등코드 메모리 : 20324 KB 시간 : 192 ms 코드길이 : 1780 B 내 코드 메모리 : 110976 KB 시간 : 728 ms 코드길이 : 1154 B >> 1등과의 차이가 너무 크다... 1등 코드 공부 꼭 하기 [1등코드] import java.io.DataInputStream; import java.io.IOException; public class ..

입력되는 배열의 인덱스를 기준으로 앞에서는 가장 긴 오름차순 배열, 뒤에서는 거꾸로 시작하는 가장 긴 오름차순 배열을 합하면 되는 문제이다. 이때 하나가 겹치므로 -1 해줘야 함. 1등코드 메모리 : 13176 KB 시간 : 76 ms 코드길이 : 4653 B 내 코드 메모리 : 14556 KB 시간 : 152 ms 코드길이 : 1284 B [상위권 코드] class Main { public static void main(String[] args) throws Exception { int N = read(); int[] arr = new int[N], lis = new int[N], tmp = new int[N]; int k, l = 0; for (int i = 0; i < N; i++) { arr[i]..

가장 긴 증가하는 부분수열에서 살짝 변형된 문제였다. DP초기화를 같은 인덱스 위치의 수를 그대로 넣어서 해주는 것만 달랐음. 1등 코드 메모리 : 13260 KB 시간 : 88 ms 코드길이 : 1033 B 내 코드 메모리 : 14944 KB 시간 : 152 ms 코드길이 : 885 [1등 코드] import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Main { static int N; static int max; static int[] arr = new int[1001]; static int[] D = ne..

DP 테이블을 사용하는 것에 익숙해지지 않아서 그런지 엄청 헤맸다. 다른 분들의 코드를 봐도 모르겠어서 한참 헤매다가 개념부터 정리 후에 재도전 함. 그리고 부분수열에 대한 정의를 이상하게 기억하고 있었음;; 수학적인 부분도 주의해서 생각하자. LIS 중 가장 기본이라고 할 수 있는 문제니까 이번에 제대로 숙지해둬서 다행이라고 생각. 그리고 배열의 길이가 1일 때를 생각 못 해서 또 틀렸다. 항상 최솟값의 경우를 한 번 더 생각하자. 그리고 n의 크기가 작아서 이중포문을 통해 해결했지만 이때의 시간복잡도가 O(N^2)이므로 n의 크기가 조금이라도 커지면 굉장히 비효율적인 코드이다. 이분탐색을 통한 해결방법도 있으니 숙지해두자. 1등 코드 메모리 : 12924 KB 시간 : 72 ms 코드길이 : 838 ..

풀이과정 K가 1일 때, 2일 때, 3일 때 ... 를 점화식으로 표현 >> DP[N][K] = DP[N-1][K-1] + DP[N-2][K-1] + ... + DP[0][K-1] >>2개로 표현할 땐 해당 수를 2개로, 3개로 표현할 땐 2개로 나눈 후 뒤의 수를 2개로 또 나눠주기 ... 1등 코드 메모리 : 13008 KB 시간 : 68 ms 코드길이 : 634 B 내 코드 메모리 : 15012 KB 시간 : 160 ms 코드길이 : 940 B [1등 코드] import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; public class Main { public static void main..