본문 바로가기

다이나믹 프로그래밍

 (34)
[백준 / 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] 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))이 되..
[백준 / BOJ] 1256 사전 문제 출처 : www.acmicpc.net/problem/1256 1256번: 사전 첫째 줄에 N, M, K가 순서대로 주어진다. N과 M은 100보다 작거나 같은 자연수이고, K는 1,000,000,000보다 작거나 같은 자연수이다. www.acmicpc.net "a","z"로만 이루어진 문자열이 수록된 사전이있다. 사전에 있는 문자열은 모두 알파벳 순서로 정렬되어있다. "a"의 갯수 N, "z"의 갯수 M이 주어질때, K번째 문자열이 무엇인지 찾는 문제다. 풀이 수학 문제였다. N과 M이 각각 100까지 갈수있기때문에. 완전탐색으로 모든 가지를 만들며 풀경우 약 10^60번 반복하며 시간안에 절대 풀지못한다. 조합을 이용해 찾고자하는 칸 만큼 건너뛰면서 K번째 문자열을 찾아야했다. 아이디어는 다음과 ..
[백준 / BOJ] 2098 외판원 순회 문제 출처 : www.acmicpc.net/problem/2098 2098번: 외판원 순회 첫째 줄에 도시의 수 N이 주어진다. (2 ≤ N ≤ 16) 다음 N개의 줄에는 비용 행렬이 주어진다. 각 행렬의 성분은 1,000,000 이하의 양의 정수이며, 갈 수 없는 경우는 0이 주어진다. W[i][j]는 도시 i에서 j www.acmicpc.net 외판원이 어느 한 도시에서 출발해 N개의 도시를 모두 거쳐 다시 원래의 도시로 돌아오는 순회 여행 경로를 계획하려고한다. 이때, 이미 방문한 도시는 재방문할수없다. 도시를 이동할때 일정한 비용이 필요할때, 외판원이 모든 도시를 거쳐 출발도시로 돌아오는 최소 비용을 구하는 문제다. 풀이 완전탐색으로 풀려고할경우, N이 최대 16이므로, 16 * 15 * 14 ..

티스토리툴바