728x90 다이나믹 프로그래밍35 [JAVA]백준 14728번: 벼락치기 www.acmicpc.net/problem/14728 14728번: 벼락치기 ChAOS(Chung-ang Algorithm Organization and Study) 회장이 되어 일이 많아진 준석이는 시험기간에도 일 때문에 공부를 하지 못하다가 시험 전 날이 되어버리고 말았다. 다행히도 친절하신 교수님께서 아래와 www.acmicpc.net 1. 문제 설명 준석이가 공부할 수 있는 총시간의 개수와 공부해야 하는 단원의 개수가 주어진다. 단원마다 단원의 문제를 맞히기 위해 필요한 공부시간과 점수가 주어진다고 하였을 때 준석이가 얻을 수 있는 최대 점수를 구하는 문제이다. 2. 풀이 간단한 DP 문제이다. dp[x] = 공부할 수 있는 시간이 x일 때 준석이가 얻을 수 있는 최대 점수 시간 복잡도 O(NT).. 2021. 3. 18. [JAVA]백준 1516번: 게임 개발 www.acmicpc.net/problem/1516 1516번: 게임 개발 첫째 줄에 건물의 종류 수 N(1 ≤ N ≤ 500)이 주어진다. 다음 N개의 줄에는 각 건물을 짓는데 걸리는 시간과 그 건물을 짓기 위해 먼저 지어져야 하는 건물들의 번호가 주어진다. 건물의 번호는 1부 www.acmicpc.net 1. 문제 설명 어떤 건물을 짓기 전에 그 건물을 짓기 전에 지어야 하는 건물들을 지은 후에 지을 수 있다. 여러 개의 건물을 동시에 지을 수 있고, 건물을 짓는 명령을 내리기까지 시간이 걸리지 않는다고 하고, 각 건물을 짓는데 걸리는 시간과 그 건물을 짓기 위해 먼저 지어져야 하는 건물들의 번호가 주어질 때, 각 건물이 완성되기까지 걸리는 최소 시간을 출력하는 문제이다. 2. 풀이 백준 2056번 .. 2021. 3. 13. [JAVA]백준 17070번: 파이프 옮기기 1 www.acmicpc.net/problem/17070 17070번: 파이프 옮기기 1 유현이가 새 집으로 이사했다. 새 집의 크기는 N×N의 격자판으로 나타낼 수 있고, 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 (r, c)로 나타낼 수 있다. 여기서 r은 행의 번호, c는 열의 www.acmicpc.net 1. 문제 설명 파이프를 옮기려고 할 때 파이프는 45도만 회전시킬 수 있다. 가장 처음 파이프는 (1,1)와 (1,2)를 차지하고 있고 파이프의 한쪽 끝을 (N, N)로 이동시키는 방법의 개수를 구해보자. 2. 풀이 dp[X][Y][3] -> (X, Y)까지 파이프를 이동시킬 수 있는 방법의 수 0 -> 가로, 1-> 세로, 2-> 대각선이라고 하자. 그렇다면 dp[x][y][0] +.. 2021. 3. 12. [JAVA]백준 7579번: 앱 www.acmicpc.net/problem/7579 7579번: 앱 입력은 3줄로 이루어져 있다. 첫 줄에는 정수 N과 M이 공백문자로 구분되어 주어지며, 둘째 줄과 셋째 줄에는 각각 N개의 정수가 공백문자로 구분되어 주어진다. 둘째 줄의 N개의 정수는 현재 활 www.acmicpc.net 1. 문제 설명 N개의 앱이 활성화되어있고 이들 앱 Ai는 각각 mi 바이트만큼의 메모리를 사용하고 있고, 앱 Ai를 비 활성하는 비용은 ci라고 하자. M 바이트 이상의 메모리를 추가로 확보하려고 할 때 비용 ci의 합의 최솟값을 구하는 문제이다. 2. 풀이 다이나믹 프로그래밍을 이용하여 풀 수 있다. cost[x] = 비용의 합이 X일 때, 추가로 확보할 수 있는 최대 메모리 = Math.min(cost [x], .. 2021. 3. 8. 이전 1 2 3 4 5 ··· 9 다음 728x90
