본문 바로가기
728x90

다이나믹 프로그래밍35

[JAVA]백준 14567번: 선수과목 (Prerequisite) www.acmicpc.net/problem/14567 14567번: 선수과목 (Prerequisite) 3개의 과목이 있고, 2번 과목을 이수하기 위해서는 1번 과목을 이수해야 하고, 3번 과목을 이수하기 위해서는 2번 과목을 이수해야 한다. www.acmicpc.net 1. 문제 설명 과목들의 선수과목 조건들이 주어질 때 모든 과목에 대해 각 과목을 이수하려면 최소 몇 학기가 걸리는지 구하는 문제. 2. 풀이 위상 정렬과 다이내믹 프로그래밍으로 풀 수 있는 문제이다. 1) 다이내믹 프로그래밍 X번 과목이 이수할 수 있는 최소 학기를 dp [X]라 할 때 dp [X]는 X의 선수과목들의 최소 학기의 최댓값 +1이다. dp [X]=MAX(dp [Y]+1) (Y는 X의 선수과목) 점화식과 선수과목 조건 A .. 2021. 2. 22.
[JAVA]백준 9184번: 신나는 함수 실행 www.acmicpc.net/problem/9184 9184번: 신나는 함수 실행 입력은 세 정수 a, b, c로 이루어져 있으며, 한 줄에 하나씩 주어진다. 입력의 마지막은 -1 -1 -1로 나타내며, 세 정수가 모두 -1인 경우는 입력의 마지막을 제외하면 없다. www.acmicpc.net 1. 문제 설명 재귀 함수 w(a, b, c)가 있는데 이 함수를 구현하는 것은 쉽다! 하지만 그대로 구현하면 값을 구하는데 오래 걸린다. a, b, c가 주어졌을 때 w(a, b, c)를 출력하라. 2. 풀이 w(a,b,c) 함수의 구현과 메모이제이션을 합쳐서 구현하면 쉽게 풀 수 있는 문제이다. a, b, c가 주어졌을 때 그 계산의 결과를 dp [a][b][c]에 저장해 두고 다음 a, b, c가 주어졌을 때.. 2021. 2. 20.
[JAVA]백준 2293번: 동전 1 www.acmicpc.net/problem/2293 2293번: 동전 1 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. www.acmicpc.net 1. 문제 설명 n 가지 종류의 동전을 적당히 사용하여 K원을 만들게 하는 경우의 수를 구하시오. 2. 풀이 2원을 사용하여 5원을 만들고자 한다면 3원까지의 합에 2원을 더해 5원을 만들 수 있다. 따라서 동전을 A1, A2.... An이라 하고, 만들고자 하는 가치의 합을 Y라고 한다면 dp [Y]=dp [Y-A1]+dp [Y-A2]+...+dp [Y-An]이다. 이 점화식을 이용하여 새로운 동전을 하나 입력.. 2021. 2. 15.
[JAVA]백준 2618번: 경찰차 www.acmicpc.net/problem/2618 2618번: 경찰차 첫째 줄에는 동서방향 도로의 개수를 나타내는 정수 N(5≤N≤1,000)이 주어진다. 둘째 줄에는 처리해야 하는 사건의 개수를 나타내는 정수 W(1≤W≤1,000)가 주어진다. 셋째 줄부터 (W+2)번째 줄까지 www.acmicpc.net 1. 문제 설명 (1,1)과 (N, N)에 두 대의 경찰차가 대기하고 있다. 그 후 W개의 사건들의 좌표들이 주어질 때 사건들이 발생한 순서대로 경찰차들이 이동하는 거리의 합의 최솟값을 출력하고 경로를 출력하는 문제이다. 2. 풀이 점화식보다 재귀함수로재귀 함수로 푸는 것이 더 간단해서 재귀 함수로 문제를 풀었다. 재귀 함수의 경우 O(N^2)의 시간복잡도를 가지지만 점화식의 경우 O(N^3)을 가.. 2021. 2. 11.
728x90

티스토리툴바