https://www.acmicpc.net/problem/7579 DP 풀이Knapsack문제를 완벽히 체득하고 외울정도까지 되었으면 이를 응용하는버전으로 구할수있다.하지만 주의해야할건 dp[i][w]에서 1~i까지 어플중에 메모리가 w일때 최소 시간 이라고 정의하면, 메모리 부족이 뜬다.dp[i][t] =  1~i까지 어플이있을때, t시간을 소요하는 최대 메모리라고 dp를 선언할수 있느냐 없느냐를 물어보는게 이문제의 핵심같다. 그렇게하면 점화식을 다음과 같이 세울 수 있다 dp[i][t] => max(dp[i -1][t - cost[i]] + memory[i] ( i번째를 담았을 때) , dp[i - 1][t] (i번째를 안담았을 때)) 그후 0이 엣지케이스이므로 index문제만 해결해주면된다. 왜 최..

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/1890 솔직히 맞을줄몰랐는데 맞아서 신기했다 어차피 오른쪽 또는 아래로만 갈수있으므로,그리디를 적용해서 메모이제이션으로 풀 수있었다. 그리디를 적용했다는것은 , 지도를 왼쪽 -> 오른쪽 , 위 -> 아래 순으로 이중 for문을 돌렸을때,한번 방문한것은 다시 방문 안해도 되는것을 깨닫고 적용해보았다. import java.io.BufferedReader;import java.io.InputStreamReader;import java.util.Arrays;public class Main { static int N; static int[][] map; static long[][] dp; public static void main(..

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 ..

https://www.acmicpc.net/problem/16928 16928번: 뱀과 사다리 게임첫째 줄에 게임판에 있는 사다리의 수 N(1 ≤ N ≤ 15)과 뱀의 수 M(1 ≤ M ≤ 15)이 주어진다. 둘째 줄부터 N개의 줄에는 사다리의 정보를 의미하는 x, y (x www.acmicpc.net    처음에 순수 DP로 풀었으나 실패해서 BFS + DP(??) 를 활용해서풀었다 import java.io.BufferedReader;import java.io.InputStreamReader;import java.util.Arrays;import java.util.LinkedList;import java.util.Queue;import java.util.StringTokenizer;public cla..