본문 바로가기

다이나믹 프로그래밍

 (34)
[백준 / BOJ] 2056 작업 문제 출처 : www.acmicpc.net/problem/2056 2056번: 작업 수행해야 할 작업 N개 (3 ≤ N ≤ 10000)가 있다. 각각의 작업마다 걸리는 시간(1 ≤ 시간 ≤ 100)이 정수로 주어진다. 몇몇 작업들 사이에는 선행 관계라는 게 있어서, 어떤 작업을 수행하기 위해 www.acmicpc.net N개의 수행할 작업과, 각 작업을 수행하는데 걸리는 시간이 주어진다. 작업에는 선행관계가 있고, 각 작업을 수행하기위해선, 해당 작업의 선행작업을 수행해야한다. 이때, 모든 작업을 수행하는데 걸리는 최소시간을 구하는 문제다. 풀이 재귀와 메모이제이션으로 풀리는문제다. 현재 작업 A를 수행해야하고 A의 선행 작업이 B,C,D라고 할때, B,C,D가 걸리는 수행시간중 최댓값을 가져와서 A가 ..
[백준 / BOJ] 1005 ACM Craft 문제 출처 : www.acmicpc.net/problem/1005 1005번: ACM Craft 첫째 줄에는 테스트케이스의 개수 T가 주어진다. 각 테스트 케이스는 다음과 같이 주어진다. 첫째 줄에 건물의 개수 N 과 건물간의 건설순서규칙의 총 개수 K이 주어진다. (건물의 번호는 1번부 www.acmicpc.net 내가 원하는 건물을 건설할때 걸리는 최소 시간을 출력하는 문제다. 풀이 완전탐색으로 풀경우 N 3 이렇게 저장이 될건데, 4번건물을 짓기위해선 4번에 연결된 건물들을 모두 지어야한다(2번과 3번)라는 뜻 2. 끝까지 탐색하며 건물을 지을때마다 check배열을 업데이트 해준다. (바텀업으로 구현함) check배열을 업데이트할때, 전 위치의 건물들중 최댓값을 뽑아서 업데이트 해줘야함 이때 이미 ..
[백준 / BOJ] 10164 격자상의 경로 문제 출처 : www.acmicpc.net/problem/10164 10164번: 격자상의 경로 입력의 첫째 줄에는 격자의 행의 수와 열의 수를 나타내는 두 정수 N과 M(1 ≤ N, M ≤ 15), 그리고 ○로 표시된 칸의 번호를 나타내는 정수 K(K=0 또는 1 < K < N×M)가 차례로 주어지며, 각 값은 공백으 www.acmicpc.net N*M 그리드에서 무조건 (1,1) 에서 시작하여 (Y,X)지점을 지나 (N,M)지점에 최소한의 이동으로 도달하는 경로의 수를 구하는 문제다. 풀이 dp로 풀리는 문제였다. 전 지점에 최소로 도달하는 경로의 수를 알고있다면, 현재위치까지 오는 경로의 수를 알수있다. 예제처럼 3*5 그리드가 있다고 가정해보자 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0..
[백준/BOJ] 11560 다항식 게임 문제 출처 : www.acmicpc.net/problem/11560 11560번: 다항식 게임 매 테스트 케이스마다 한 줄에 걸쳐 다항식 \(p(x) = (1+x)(1+x+x^2)(1+x+x^2+x^3)\dots(1+x+\dots+x^{k-1}+x^k)\)의 \(x^N\)항의 계수를 출력한다. www.acmicpc.net k에 따라 다항식이 연결된다. k = 0 (1) k = 1 (1)(1+x) k = 2 (1)(1+x)(1+x+x^2) k = 3 (1)(1+x)(1+x+x^2)(1+x+x^2+x^3) . . . k = ? 일때의 다항식을 계산한 결과에서 N차항의 계수를 출력하는 문제다. 풀이 k = 20 , N = 210까지 간다. k가 늘어남에따라, 곱해야하는 항의 차수 또한 매우 늘어나므로, 완탐으..
[백준 / BOJ] 11062 카드게임 문제 출처 : www.acmicpc.net/problem/11062 11062번: 카드 게임 근우와 명우는 재미있는 카드 게임을 하고 있다. N개의 카드가 일렬로 놓여 있다. 각 카드에는 점수가 적혀있다. 근우부터 시작하여 번갈아가면서 턴이 진행되는데 한 턴에는 가장 왼쪽에 있는 � www.acmicpc.net 근우와 명우는 카드게임을 하고있다. 근우부터 시작하여 번갈아가면서 카드를 선택하는데, 이때 서로가 최선의 전략으로 임할때 근우가 얻는 최대점수를 구하는문제다. (단, 남아있는 카드중 가장 오른쪽과 가장끝만 선택할수있다.) 풀이 어려웠던 문제였다. 서로가 항상 최선의 전략으로 임한다고 하는데, 어떤 걸 선택해야 최선의 상황이 되는지 모르기 때문에 모든경우를 다 봐줘야한다. 플레이어(근우와 명우)는 ..
[백준 / BOJ] 2611 자동차 경주 문제 출처 : www.acmicpc.net/problem/2611 2611번: 자동차경주 첫째 줄에는 지점의 개수 N이 주어진다. 각 지점에는 1부터 N까지의 서로 다른 번호가 부여된다. 둘째 줄에는 도로의 개수 M이 주어진다. 이어 M개의 줄에는 p ,q ,r의 형식으로 도로의 정보가 주어 www.acmicpc.net N개의 지점이 있는 그래프가 주어진다. 각 지점사이를 연결하는 도로에는 그 도로를 지날때 얻는 점수가 있다. 1번지점에서 출발해서 다시 1번지점으로 돌아올때, 가장 많이 얻을수있는 점수와, 그때의 경로를 출력하는 문제다. 도로는 단방향 이다. 풀이 dp배열에 (dp[idx] = idx까지 도착했을때 얻은 최대 점수) 를 저장해준다. DFS를 돌리며, dp[현재 도로에 도착했을때 까지 얻은..
[백준 / BOJ] 17485 진우의 달 여행 (Large) 문제 출처 : www.acmicpc.net/problem/17485 17485번: 진우의 달 여행 (Large) 첫줄에 지구와 달 사이 공간을 나타내는 행렬의 크기를 나타내는 N, M (2 ≤ N, M ≤ 1000)이 주어진다. 다음 N줄 동안 각 행렬의 원소 값이 주어진다. 각 행렬의 원소값은 100 이하의 자연수이다. www.acmicpc.net 진우가 지구에서 출발해서 달에 도착했을때, 필요한 자금을 최소화 하는문제다. 달에서 지구까지 가는길에 각 칸에 자금이 주어진다. 풀이 N,M이 각각 최대 1000이고, 한 인덱스에서 아래로 갈수있는방향이 3가지 (왼쪽아래 오른쪽아래 중간) 이므로 완전탐색으로 풀려고하면 시간초과가 난다. 다이나믹 프로그래밍으로 풀어야 했는데, dp배열을 구현하고 사용하는게 힘..
[백준 / BOJ] 13325 이진트리 문제 출처 : www.acmicpc.net/problem/13325 13325번: 이진 트리 문제 각 에지에 양수인 가중치가 부여된 높이가 k인 포화이진트리가 주어져 있다. 높이 k인 포화이진트리는 2k개의 리프를 포함하여 (2k+1 − 1)개의 노드를 가진다. 루트에서 어떤 리프까지의 거�� www.acmicpc.net 1~K높이의 이진트리가 주어졌을때, 한 루트에서 어떤 리프까지의 거리는 루트에서 그 리프까지의 경로상에 있는 모든 에지들의 가중치를 더한 값이다. 각 에지들의 가중치를 증가시켜서 루트에서 모든 리프까지의 거리가 모두 같게하면서 에지의 가중치합을 최소로 만드는 문제다. 풀이 (백준에서 1초에 반복문이 1억번 돈다고 들은것같다..) 최악의 경우인 1^1 + 1^2 + 1 ^ 3 + ... ..

티스토리툴바