본문 바로가기
반응형

동적 계획법23

[C/C++] 백준 #2294 동전 2(동적 계획법) #2294 동전 문제도 #2293 동전 문제와 비섯합니다. 단, 가치가 같은 동전이 주어질 수 있다는 것 뿐으로 크게 고려 대상은 아닙니다. 문제의 링크입니다. https://www.acmicpc.net/problem/2294 2294번: 동전 2 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. 가치가 같은 동전이 여러 번 주 www.acmicpc.net 참고할 수 있는 이전 문제 링크입니다. https://sdev.tistory.com/1333 [C/C++] 백준 #2293 동전 1(동적 계획법) 동전들을 가지고 만들 수 있는 돈의 액수의 경우의 수는 동적 .. 2023. 4. 20.
[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.
728x90

티스토리툴바