728x90 다이나믹 프로그래밍35 [JAVA]백준 15724번: 주지수 www.acmicpc.net/problem/15724 15724번: 주지수 네모 왕국의 왕인 진경대왕은 왕국의 영토를 편하게 통치하기 위해서 1X1의 단위 구역을 여러 개 묶어서 하나의 거대 행정구역인 주지수(州地數, 마을의 땅을 셈)를 만들 예정이다. 진경대왕은 www.acmicpc.net 1. 문제 설명 네모 왕국의 영토 1*1 단위 구역이 주어지고 단위 구역마다 살고 있는 사람 수가 주어진다. X1, Y1, X2, Y2좌표가 주어질 때 주어진 직사각형 범위에 살고 있는 사람의 수를 구하여라. 2. 풀이 dp[x][y]= X1=1, Y1=1, X2=x, Y2=y 직사각형 범위에 살고 있는 사람의 수 = dp[x-1][y]+dp[x][y-1]+x,y 좌표에 살고 있는 사람 수 -dp [x-1][y-1].. 2021. 3. 2. [JAVA]백준 1823번: 수확 www.acmicpc.net/problem/1823 1823번: 수확 첫째 줄에 벼의 개수 N(1 ≤ N ≤ 2,000)이 주어지고 두 번째 줄부터 N+1번쨰 줄까지 벼의 가치 v(i) (1 ≤ v(i) ≤ 1,000) 가 주어진다. www.acmicpc.net 1. 문제 설명 1*N 크기의 긴 밭에 심어진 벼를 수확하려고 한다. 벼는 양끝에 있는 벼만 수확을 할 수 있다. 수확을 하였을 때 얻을 수 있는 이익은 벼의 가치 v(i) * 벼를 수확한 순서 k의 합이다. 벼를 수확할 때 얻을 수 있는 최대 이익을 구하시오. 2. 풀이 dp로 Top down 방식과 Bottom Up 방식으로 풀 수 있다. 1) Top down (재귀) cut(start, end, num) = 현재 남은 벼가 start 인덱스.. 2021. 2. 26. [JAVA]백준 18427번: 함께 블록 쌓기 www.acmicpc.net/problem/18427 18427번: 함께 블록 쌓기 첫째 줄에 자연수 N, M, H가 공백을 기준으로 구분되어 주어진다. (1 ≤ N ≤ 50, 1 ≤ M ≤ 10, 1 ≤ H ≤ 1,000) 둘째 줄부터 N개의 줄에 걸쳐서 각 학생이 가진 블록들의 높이가 공백을 기준으로 구 www.acmicpc.net 1. 문제 설명 N명의 학생들이 최대 M개의 블록을 가지고, 한 학생당 최대 1개의 블록만을 사용할 수 있을 때 (사용하지 않는 경우도 가능) 높이가 정확히 H인 탑을 만드는 경우의 수를 구하는 문제. 2. 풀이 dp를 이용해서 간단하게 풀 수 있는 문제이다. 1번부터 X 학생까지 높이 Y인 탑을 만들 수 있는 경우의 수를 dp [X][Y]라 하고, X학생이 가진 블록을 .. 2021. 2. 26. [JAVA]백준 2056번: 작업 www.acmicpc.net/problem/2056 2056번: 작업 수행해야 할 작업 N개 (3 ≤ N ≤ 10000)가 있다. 각각의 작업마다 걸리는 시간(1 ≤ 시간 ≤ 100)이 정수로 주어진다. 몇몇 작업들 사이에는 선행 관계라는 게 있어서, 어떤 작업을 수행하기 위해 www.acmicpc.net 1. 문제 설명 수행해야 할 작업 N개와 각각의 작업마다 걸리는 시간, 어떤 작업 X를 수행하기 전에 반드시 먼저 완료되어야 할 작업들이 주어졌을 때 모든 작업을 완료하기 위해 필요한 최소 시간을 구하는 문제. 2. 풀이 kwoncorin.tistory.com/75 [JAVA]백준 14567번: 선수과목 (Prerequisite) www.acmicpc.net/problem/14567 14567번: 선수.. 2021. 2. 25. 이전 1 2 3 4 5 6 7 ··· 9 다음 728x90
