https://www.acmicpc.net/problem/2629  추를 (저울에 올리지 않는경우) , (오른쪽에 올리는 경우), (왼쪽에 올리는 경우)총 세개로 재귀함수를 돌리면되는데, 그렇게 하면 문제의 조건에의해 시간 초과가 나므로, 메모이제이션을통해 가지치기를 해야한다  dp[i][w] = i번째 추까지 있을때, 그것으로 만들수있는 무게 w dp[i][w]의 의미를 제대로 규정짓지못해서 풀기 어려웠던 문제였다..  import java.io.BufferedReader;import java.io.InputStreamReader;public class Main { static int N; static int[] weight; static boolean[][] dp; static ..

https://www.acmicpc.net/problem/1446   점화식을 세울 수 있다.dp는 나름대로 노하우가 생겼는데1) dp배열이 의미하는것이 무엇인지를 명확히 세우는것이 중요하고,2) 항상 i 와 i + 1의 관계를 생각하면 잘 떠오르는것같다. 최대한 다른것들은 배제하고, 컴팩트하게 i 와 i + 1의 관계만을 생각하면 된다.  제일 중요한것은 dp[i]가 무엇인지 정의를 해야한다, dp[i]란 i까지 도착하는데 걸리는 최솟길이 라고 정의했다. 그다음 점화식을 세워야 한다. 최대한 i 와 i + 1 관계 외에 다른 복잡한 생각을 지웠더니 은근히 잘 떠오를 수 있었다.점화식1) (도착점이 i인 지름길이 존재할 때) ->  dp[i] = min(dp[i] , dp[지름길의 시작점] + 지름길의 ..

https://www.acmicpc.net/problem/1520  단순히 DFS 완전탐색으로 풀었지만 메모리 초과가 난다. 이유는 완전탐색DFS의 경우, 각 칸에서 최악의경우 O(N x M)번의 탐색을 해야한다.각 칸을 여러 번 중복해서 탐색할 수 있기 때문에, 최악의 경우 각 칸에 대해 O(N×M) 수행을 한다. 총 칸수는 N x M개이기 때문에 O((N x M) x (N x M)))의 시간 복잡도가 발생하게 된다. 즉 , 최악의경우 500 * 500 * 500 * 500 = 62,500,000,000 => 625억 이므로, 제한시간인 2초를 1초에 1억이라고 했을때 625억 >> 2억이므로 (625초 >> 2초) 당연히 시간초과(혹은 스택이 무한적 쌓이므로 메모리 초과)가 난다. 이 문제는 dfs를..

import java.io.BufferedReader;import java.io.InputStreamReader;import java.util.Arrays;import java.util.StringTokenizer;public class Main { public static void main(String[] args) throws Exception { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int[][] dp; // 마지막 상자가 i번째인 가장 큰 가치 . int[] weight; int[] value; for (int k = 1; k = weight[i]) { //i번째 인덱스를 넣을수 있다면 ..

https://www.acmicpc.net/problem/2096   맨 처음 풀었을떄 코드 :  bfs -> 메모리초과import org.w3c.dom.Node;import java.io.BufferedReader;import java.io.InputStreamReader;import java.util.*;public class Main { public static int N; public static int[][] map; public static int max = Integer.MIN_VALUE; public static int min = Integer.MAX_VALUE; public static Queue queue = new LinkedList(); public ..