DP

https://www.acmicpc.net/problem/16930 16930번: 달리기 진영이는 다이어트를 위해 N×M 크기의 체육관을 달리려고 한다. 체육관은 1×1 크기의 칸으로 나누어져 있고, 칸은 빈 칸 또는 벽이다. x행 y열에 있는 칸은 (x, y)로 나타낸다. 매 초마다 진영이는 www.acmicpc.net 문제 풀이 이 문제에서 내가 집은 포인트는 3 가지이다. 1. 우선 순위 큐를 이용하여 최대한 시간이 덜 걸리는 순으로 처리하는 것 (우선순위큐 bfs 다익스트라 이용) 2. dp배열을 이용해서 이미 왔던 곳이면 break를 거는 것 3. 이중 for 문을 이용해서 nextX,nextY를 정할 때 , 1부터~k까지 이동가능한 모든 경우를 큐에 넣는 것 1 2 3 4 5 6 7 8 9 1..

https://www.acmicpc.net/problem/15989 15989번: 1, 2, 3 더하기 4 정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 4가지가 있다. 합을 나타낼 때는 수를 1개 이상 사용해야 한다. 합을 이루고 있는 수의 순서만 다른 것은 같은 것으로 친다. 1+1+1+1 2+1+1 (1+1+2, 1+2+1) 2+2 www.acmicpc.net 풀이 전형적인 dp문제이다. 우선 단순 노가다로 풀어보다가 3번쨰마다 규칙이 있을거라는 추측을해본다. 두번째마다 1씩 올라가는 걸 확인 할 수 있다. 이걸 점화식으로 세우면 다음과 같다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 import java.util.*; imp..

문제 풀이 1. 이 문제는 bfs와 같은 일반적인 그래프 탐색으로 접근하면 시간초과가 나버린다.. -> dp 문제 2. 경로의 개수는 263-1보다 작거나 같으므로 dp의 자료형을 long으로 선언 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 import java.util.*; import java.io.*; public class Main{ static int N; static int[][] map; static long[][] dp; public static void main(String[] args) throws IOException { BufferedReader br = ..

이 문제는 DFS + DP 문제이다. 여기서 DP는 최대 생존가능일 수를 기록. 기본적으로 , 입력을 map으로 받았을때, 다음 이동해야 하는 방향의 값이 지금의 값보다 더 커야한다. 즉 , map[y][x] < map[nextY][nextX] 가 성립 해야 한다. 그리고 탐색했던곳을 중복탐색하는 것을 막기위해 메모이제이션 기법으로 dp를 바로 반환해주는것이 핵심이다. 그렇지 않으면 시간초과 발생. if(dp[y][x] != 1) return dp[y][x]; dfs로 탐색했을때 , 현재 기록된 생존가능일 수 보다 더 오래 살 수 있으면 갱신. dp[y][x] = Math.max(dfs(nextX,nextY)+1,dp[y][x]); 처음에 바로 떠 올리기엔 쉽지 않은 문제이다. 12345678910111..