본문 바로가기
반응형

동적 계획법22

[C/C++] 백준 #2293 동전 1(동적 계획법) 동전들을 가지고 만들 수 있는 돈의 액수의 경우의 수는 동적 계획법을 이용하는 대표적 문제 중 하나입니다. 문제의 링크입니다. https://www.acmicpc.net/problem/2293 2293번: 동전 1 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. www.acmicpc.net 주어진 K원을 만들기 위해서는 동전의 종류를 먼저 조절해야 합니다. 서로 다른 동전의 종류가 n개가 있다면, 우리는 동적 계획법의 변수 \(d_{n, k}\)를 정의하도록 합니다. n개의 동전을 가지고 k 금액을 만드는 경우의 수로 정의토록 합니다. 이렇게 하면 다음과 갈은.. 2023. 4. 20.
[C/C++] 백준 #2169 로봇 조종하기(동적 계획법) #2169 문제는 동적 계획법을 이용했지만, 일반적인 동적 계획법은 한방향으로만 진행되는 경우에 주로 사용됩니다. 이 문제에서는 한곳의 값을 결정하기 위해서는 왼쪽, 오른쪽, 그리고 위라는 3군데 방향을 고려해야 하므로 좀 까다롭습니다. 문제의 링크입니다. https://www.acmicpc.net/problem/2169 2169번: 로봇 조종하기 첫째 줄에 N, M(1≤N, M≤1,000)이 주어진다. 다음 N개의 줄에는 M개의 수로 배열이 주어진다. 배열의 각 수는 절댓값이 100을 넘지 않는 정수이다. 이 값은 그 지역의 가치를 나타낸다. www.acmicpc.net 문제는 나사(NASA)의 로봇이 화성을 돌아다닐때, 최대한의 가치를 얻으면서 지역을 탐사하는 것입니다. 처음에 어떻게 짜야할까 고민하.. 2023. 4. 12.
[C/C++] 백준 #2156 포도주 시식(탐욕 알고리즘) 이번 문제는 탐욕 알고리즘의 범주로 놓아야할 것 같아서, 탐욕 알고리즘이라고 적기는 했지만, 문제에서 추천하는 알고리즘은 동적 계획법입니다. 동적 계획법이 더 맞을 수도 있겠죠. 문제의 링크는 다음과 같습니다. https://www.acmicpc.net/problem/2156 2156번: 포도주 시식 효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규 www.acmicpc.net 제가 생각한 알고리즘은 다음과 같습니다. \(fc_0\)은 현재 와인을 선택하지 않았을 때, 최대값입니다. \(fc_1\)은 이전 와인은 선택하지 않았지만, 현재 와인은 선택한 경우입니다. .. 2023. 4. 10.
[C/C++] 백준 #2096 내려가기(동적 계획법) 내려가기 문제는 간단한 형태의 동적 계획법(Dynamic Programming)을 사용하면 됩니다. 동적 계획법을 사용하지 않고, DFS나 BFS를 이용해서 풀 수는 있지만, 그렇게 하면 시간이 많이 걸립니다. 다익스트라 알고리즘을 사용해도 동적 계획법을 적용한 것과 같은 효과를 낼 수 있습니다. https://www.acmicpc.net/problem/2096 2096번: 내려가기 첫째 줄에 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 숫자가 세 개씩 주어진다. 숫자는 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 중의 하나가 된다. www.acmicpc.net 처음에는 설명을 이해하기 어려웠습니다. 주어진 N이 주어지면, 3xN 형태의 공간이 발생합니다. 맨 위층에서는 3칸.. 2023. 3. 30.
[C/C++] 백준 #2011 암호코드(동적 계획법) 영문 대문자로만 이루어진 암호가 있으면, 해당 영문자를 A는 1로 B는 2로 Z는 26으로 차례대로 숫자를 지정한다면, 숫자를 나열할 수 있습니다. 예를 들어서 BEAN은 B는 2, E는 5, A는 1, N은 14이므로 25114로 표현할 수 있죠. 하지만, Y = 25, K = 11, D = 4 이므로 YKD도 될 수 있죠. 숫자가 주어졌을 때, 그것을 영문자로 바꿀 수 있는 경우는 제한되어 있습니다. 일단 0을 제외한 한자리 숫자는 모두 영문으로 만들 수가 있겠죠. 두자리 숫자가 26을 초과한다면 이 경우에는 J 이상의 영문자로 만들 수가 없으므로 한자리 숫자로 해야 합니다. 그리고 바꿀 수 없는 경우도 있습니다. 304와 같은 숫자는 나올 수 있는 영문 단어가 없습니다. 30은 글자가 안 되고, 0.. 2023. 1. 15.
[C/C++] 백준 #1937 욕심쟁이 판다(동적 계획법) 격자로 나누어진 공간에서 판다가 대나무를 먹는데, 옮긴곳이 이전보다 대나무가 더 많은 곳이어야 옮겨갈 수 있습니다. 판다는 이동을 할 때, 상하좌우중 하나를 선택해서 한칸만 옮겨갈 수 있습니다. 이 판다가 최대한 많은 대나무숲에서 식사를 할 수 있도록 하고자 할 때, 최대 이동횟수를 구하는 문제입니다. 조금 어려워보이지만, 전 일단 탐욕 방법을 사용했습니다. 판다가 처음 위치한 곳의 대나무숲이 적은 곳이어야 한다는 것이죠. 그래서 최대로 많은 곳까지 가는 대나무숲을 고르는 것이죠. \(V(s)\)의 값이 현재까지 이동한 횟수를 저장한다고 한다면, \[ V(s) = max_{s \rightarrow s'}(V(s'))+1 형태로 작성할 수 있습니다. 이것을 동적 계획법으로 풀기 위해서는 가장 적은 값부터 .. 2022. 11. 17.
728x90

티스토리툴바