본문 바로가기

DP

(45)
[백준 / BOJ] 7579 앱 (Java) 문제 출처 : https://www.acmicpc.net/problem/7579 7579번: 앱 입력은 3줄로 이루어져 있다. 첫 줄에는 정수 N과 M이 공백문자로 구분되어 주어지며, 둘째 줄과 셋째 줄에는 각각 N개의 정수가 공백문자로 구분되어 주어진다. 둘째 줄의 N개의 정수는 현재 활 www.acmicpc.net 스마트폰 백그라운드에 켜져있는 N개의 애플리케이션중 몇개의 애플리케이션을 종료해서 M만큼의 메모리를 확보하고싶다. 각 애플리케이션을 종료할때얻는 메모리양과 종료할때 필요한 비용이 주어질때, M만큼의 메모리를 확보하기위해 필요한 최소 비용을 구하는 문제다. 풀이 knapsack 문제였다. 개인적으로 dp배열을 생각하는게 어려웠다. 2차원 배열을 이용해 푸는것은 맞는것 같은데, M이 10,00..
[백준 / BOJ] 5852 Island Travels (Java) 문제 출처 : https://www.acmicpc.net/problem/5852 5852번: Island Travels Farmer John has taken the cows to a vacation out on the ocean! The cows are living on N (1
[백준 / BOJ] 4883 삼각 그래프 (Java) 문제 출처 : https://www.acmicpc.net/problem/4883 4883번: 삼각 그래프 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 그래프의 행의 개수 N이 주어진다. (2 ≤ N ≤ 100,000) 다음 N개 줄에는 그래프의 i번째 행에 있는 정점의 비용이 www.acmicpc.net N(N>=2)개의 행, 3개의 열로이루어진 삼각그래프 가있다. 삼각그래프의 각 노드는, (y,x일때) 자신의 위치기준으로 (0, -1) (-1, -1) (-1, 0) (-1, 1)위치에 있는 노드들에서 올수있다. (해당 위치에 노드가 없는경우 올수없다.) 각 노드에 가중치가 있을때, (1,2)위치부터 (N,2)위치까지 가는 최소경로를 구하는 문제다. 풀이 다이나믹 프..
[백준 / BOJ] 1103 게임 문제 출처 : https://www.acmicpc.net/problem/1103 1103번: 게임 줄에 보드의 세로 크기 N과 가로 크기 M이 주어진다. 이 값은 모두 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 보드의 상태가 주어진다. 쓰여 있는 숫자는 1부터 9까지의 자연수 또는 www.acmicpc.net 형택이는 1~9까지의 숫자와 구멍이 있는 직사각형 보드에서 게임을 한다. 보드의 1,1위치에 동전을 하나 올려놓고, 동전을 다음과 같이 움직인다. - 동전이 놓인 위치에 있는 숫자만큼 위,아래,왼쪽,오른쪽 위치로 움직인다. (이 과정에서 구멍은 무시한다.) - 동전이 이동한 위치에 구멍이 있거나 동전이 보드 밖으로 나가면 게임이 종료된다. 형택이가 동전을 최대 몇번 움직일 수 있는지..
[백준 / BOJ] 14501 퇴사 문제 출처 : https://www.acmicpc.net/problem/14501 14501번: 퇴사 첫째 줄에 백준이가 얻을 수 있는 최대 이익을 출력한다. www.acmicpc.net 백준이는 오늘부터 N+1일째 되는 날 퇴사를 하기위해 남은 N일동안 최대한 많은 상담을 하려고 한다. 상담은 상담을 완료하는데걸리는시간 Ti와 이때 얻을수있는 금액 Pi로 이루어져있다. 하나의 상담을 하는중 다른상담은 할수없다. 이때, 백준이가 N일동안 상담을했을때 얻을 수 있는 최대 수익을 구하는 프로그램을 작성하시오. 소스코드 다이나믹 프로그래밍으로 풀은문제다. 일반적인 완전탐색으로 풀경우, 15!번 반복해서 시간초과가 난다. 현재 일을 Ni, dp[Ni] = Ni일 까지의 최댓값 이라고하자. 현재 날(N(i))부터..
[백준 / BOJ] 1102 발전소 문제 출처 : www.acmicpc.net/problem/1102 1102번: 발전소 은진이는 발전소에서 근무한다. 은진이가 회사에서 잠깐 잘 때마다, 몇몇 발전소가 고장이난다. 게다가, 지금 은진이의 보스 형택이가 은진이의 사무실로 걸어오고 있다. 만약 은진이가 형택이 www.acmicpc.net 은진이의 회사에는 N개의 발전소가 있다. 은진이가 회사에서 잘때마다 몇몇 발전소가 고장이난다. 이때, 고장난 발전소는 고장나지않은 발전소를 이용해 고칠수있으며, 일정한 비용이 발생한다. 적어도 P개 이상의 발전소가 고장나 있지 않도록 발전소를 고치는 최소비용을 구하는 문제다. 풀이 dp로 풀은문제다. 그리디로는 해결하지못하는데, 현재 경로가 더 많은 비용을 필요로 하더라도 결과적으로 더 작은 비용으로 발전소를..
[백준 / BOJ] 2169 로봇 조종하기 문제 출처 : https://www.acmicpc.net/problem/2169 2169번: 로봇 조종하기 첫째 줄에 N, M(1≤N, M≤1,000)이 주어진다. 다음 N개의 줄에는 M개의 수로 배열이 주어진다. 배열의 각 수는 절댓값이 100을 넘지 않는 정수이다. 이 값은 그 지역의 가치를 나타낸다. www.acmicpc.net NASA의 화성탐사로봇은 N*M배열의 화성을 탐사할려한다. N*M배열의 각 칸에는 절댓값이 100을 넘지않는 정수들이 쓰여있고, 이 값은 그 칸을 방문했을때 얻을수있는 가치와 같다. 화성탐사로봇이 (1,1)위치에서 (N,M)위치까지 탐사할때, 얻을수있는 최대 가치를 구하는 문제였다. 풀이 얼핏?보면 그래프 문제같지만, 음수가중치가 존재하므로, dp로 풀어야했던 문제였다. 문..
[백준 / BOJ] 2560 짚신벌레 문제 출처 : https://www.acmicpc.net/problem/2560 2560번: 짚신벌레 첫째 줄에 a, b, d, N을 나타내는 네 정수가 빈칸 하나를 사이에 두고 차례로 주어진다. 단, 0<a<b<d≤10,000이고, 1≤N≤1,000,000이다. www.acmicpc.net 한 생물학자가 새로 발견된 짚신벌레에 대해 연구하고있다. 짚신벌레는 1. 태어난지 a일째 되는날부터 새로운 개체를 생성한다. 2. 태어난지 b일째 되는날부터 새로운 개체생성을 중지한다(a일부터 b-1일 까지 개체를 생성함) 3. 태어난지 d일째 되는날 죽는다. 수조안에 짚신벌레가 한마리 있다할때, N일 지난후 살아있는 짚신벌레 개체수를 구하는 문제다. 풀이 완전탐색으로 풀경우, d*d*N = O(N*(d^2))이 되..