https://www.acmicpc.net/problem/12865   알고리즘 분류다이나믹 프로그래밍배낭 문제 풀이대표적인 DP 알고리즘을 사용하는 배낭 문제이다.Bottom-UP 방식을 사용했고 DP의 SubProblem은 물건을 담을 때나 담지 않을 때를 생각했다. 예시는 백준에 나와있는 입출력을 기준으로 아래의 표와 함께 설명하겠다.  초기 상태 (행 0): DP 테이블의 첫 번째 행은 물건을 하나도 고려하지 않은 상태이다. 따라서 모든 값이 0으로 초기화되어 있다. 당연히 배낭의 무게가 얼마이든지 물건을 하나도 넣지 않으면 가치는 0이기 때문이다.물건 \ 무게01234567X00000000 물건 1 (무게 6, 가치 13) - 행 1:배낭의 무게가 1부터 5까지는 물건 1의 무게(6)를 담을 수..

https://www.acmicpc.net/problem/14501 14501번: 퇴사첫째 줄에 백준이가 얻을 수 있는 최대 이익을 출력한다.www.acmicpc.net 알고리즘 분류다이나믹 프로그래밍 풀이    public class Main{ public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int n = Integer.parseInt(br.readLine()); int [] day = new int[n]; int [] money = new int[n]; ..

https://www.acmicpc.net/problem/2725 2725번: 보이는 점의 개수 첫째 줄에 테스트 케이스의 개수 C(1

https://www.acmicpc.net/problem/1577 1577번: 도로의 개수 첫째 줄에 도로의 가로 크기 N과 세로 크기 M이 주어진다. N과 M은 100보다 작거나 같은 자연수이고, 둘째 줄에는 공사중인 도로의 개수 K가 주어진다. K는 0보다 크거나 같고, 50보다 작거나 같은 자 www.acmicpc.net 알고리즘 분류 다이나믹 프로그래밍(dp) 풀이 처음에 dfs로 문제를 풀어야 되나 싶었지만 범위를 보고 dp문제임을 깨달았다. 먼저 초기화 작업이다. 가짓수를 저장하는 2차원 배열 dp이다. int형으로는 표현하기 어렵기때문에 long형으로 선언했다. 그리고 세로로 공사중인 곳을 저장하기 위한 horizontal, 가로로 공사중인 곳을 저장하귀 위한 vertical 배열을 선언해줬..