DP
-
내리막 길백준알고리즘 2019. 12. 30. 00:50
https://www.acmicpc.net/problem/1520 1520번: 내리막 길 여행을 떠난 세준이는 지도를 하나 구하였다. 이 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 한 칸은 한 지점을 나타내는데 각 칸에는 그 지점의 높이가 쓰여 있으며, 각 지점 사이의 이동은 지도에서 상하좌우 이웃한 곳끼리만 가능하다. 현재 제일 왼쪽 위 칸이 나타내는 지점에 있는 세준이는 제일 오른쪽 아래 칸이 나타내는 지점으로 가려고 한다. 그런데 가능한 힘을 적게 들이고 싶어 항상 높이가 더 낮은 지점으로만 이동하여 목표 지 www.acmicpc.net 사실 조금 전형적인 DP라고 볼수도 있겠다. 이런것들을 연습하면서 DP유형이 DP의 기본이다. 하향식으로 문제를 풀었고, 재귀 연습이 ..
-
진우의 달 여행(Large)백준알고리즘 2019. 10. 9. 22:35
https://www.acmicpc.net/problem/1748517485번: 진우의 달 여행 (Large)첫줄에 지구와 달 사이 공간을 나타내는 행렬의 크기를 나타내는 N, M (2 ≤ N, M ≤ 1000)이 주어진다. 다음 N줄 동안 각 행렬의 원소 값이 주어진다. 각 행렬의 원소값은 100 이하의 자연수이다.www.acmicpc.net 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859#include#include using namespace std; int n, m;int map[1002][1000];int dist[1002][1000];int d[1..
-
숨바꼭질2백준알고리즘 2019. 9. 1. 23:55
전형적인 BFS 문제랑은 조금 다른문제다. 전에 풀었던, 숨바꼭질4는 트랙킹, 그리고 DSLR은 트랙킹이아닌 하면서 경로 같이쓰기 하지만 이문제는 경로에 관한 정보가아닌 경로의 가짓수를 물어본다. 경로의 가짓수는 잘알고있듯 , DP로 푸는게 빠른편인데, BFS를 해서 최소 가짓수를 구하고, 가짓수를 구하는 동안에 DP를 사용해서 가짓수도구할수있다. 사실 2차원배열문제였다면 많이 어려웠을거 같다는 생각이 들지만, 1차원이라 DP도 쓰기편했다. #include #include #include #include #include using namespace std; bool d[1000000]; int go[1000000]; int cnt[1000000]; int ans = 0; int su, little; vo..
-
퇴사백준알고리즘 2019. 7. 21. 03:30
import java.util.Scanner; public class Main { static int k = Integer.MIN_VALUE; static void go(int n,int[] t , int[] p,int day, int pay){ if(day == n ){ if(pay > k) k = pay; return; } if(day > n) return; go(n,t,p,day+t[day], pay+p[day]); go(n,t,p,day + 1 , pay); } public static void main(String[] args){ Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int[] t = new int[n]; int[] p = ne..
-
기지국백준알고리즘 2019. 7. 14. 23:33
#include #include #include #include using namespace std; typedef pair PAIR; #define X first #define Y second int n; PAIR b[10005]; int d[10005]; int main(){ scanf("%d", &n); for(int i = 0; i < n; i++){ scanf("%d %d", & b[i].X, &b[i].Y); if(b[i].Y < 0) { b[i].Y = -b[i].Y; } } sort(b, b + n ); d[0] = b[0].Y * 2; for(int i = 1; i < n ; i++){ int mx_height = b[i].Y; d[i] = d[i-1] + b[i].Y *2; for(in..