반응형 dynamic programming20 [C/C++] 백준 #2579 계단 오르기(동적 계획법) 계단 오르기 조건들이 주어지면서, 계단에 적힌 값을 최대, 또는 최소가 되도록 하는 문제들이 꽤 많습니다. 보편적으로 이러한 문제들은 동적 계획법을 이용해서 풀 수 있습니다. 백준 사이트에서 주어진 문제 링크입니다. https://www.acmicpc.net/problem/2579 2579번: 계단 오르기 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점 www.acmicpc.net 계단 오르기의 조건은 1) 한계단 내지 두계단을 밟을 수 있다. 2) 연속된 3개의 계단을 밟을 수 없다. 3) 도착 계단을 반드시 밟아야 한다. 입니다. 이것을 동적 계획법으로 풀기 위해서는 최.. 2023. 11. 9. [C/C++] 백준 #2502 떡 먹는 호랑이(구현) 이번 문제는 알고리즘이 무엇이라고 이야기하기가 어렵습니다. 그냥 구현이라고 하도록 하겠습니다. https://www.acmicpc.net/problem/2502 2502번: 떡 먹는 호랑이 첫줄에 첫 날에 준 떡의 개수 A를 출력하고 그 다음 둘째 줄에는 둘째 날에 준 떡의 개수 B를 출력한다. 이 문제에서 주어진 D, K에 대해서는 항상 정수 A, B (1≤ A ≤ B)가 존재한다. www.acmicpc.net 피보나치 수열은 동적 계획법(dynamic programming)이나 재귀함수(recursion)이 나올 때 자주 등장하는 문제입니다. 일반적으로는 첫번째 항이 1, 두번째 항이 1인 경우입니다. 이번 문제는 d번째 항의 값이 주어졌을 때, 가능한 첫번째 항과 두번째 항 중 하나를 출력하면 됩니.. 2023. 5. 28. [C/C++] 백준 #2482 색상환(동적 계획법) 색상환 문제는 중복조합 문제입니다. 중복조합 문제는 식만 잘 세우면, 조합으로 문제를 해결할 수 있습니다. https://www.acmicpc.net/problem/2482 2482번: 색상환 첫째 줄에 N색상환에서 어떤 인접한 두 색도 동시에 선택하지 않고 K개의 색을 고를 수 있는 경우의 수를 1,000,000,003 (10억 3) 으로 나눈 나머지를 출력한다. www.acmicpc.net 색상환이 있습니다. 이 색상환은 비슷한 색들이 순차적으로 바뀌면서 쭉 이어지게 환(ring)을 이루게 됩니다. 색상환에 있는 모든 색은 이웃한 색과 비슷합니다. 그래서 이 색상환에서 몇개의 색을 고를때 이웃한 색을 고르지 않으려고 합니다. 고르는 경우의 수가 얼마가 되는지가 문제입니다. 환을 이루지 않는 경우에는 .. 2023. 5. 22. [C/C++] 백준 #2410 2의 멱수의 합(동적 계획법) #2410 문제는 점화식을 잘 세우면 동적 계획법을 이용해서 풀 수 있습니다. 하지만 늘 그렇듯이 점화식을 만드는 과정이 쉽지만은 않습니다. https://www.acmicpc.net/problem/2410 2410번: 2의 멱수의 합 첫째 줄에 경우의 수를 출력한다. 답이 커질 수 있으므로 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 어떤 수가 주어지면, 그 수를 2의 멱승(1, 2, 4, 8, ...과 같이 \(2^k\)으로 표현되는 수)의 합으로 표시하는 경우의 수를 구하는 것입니다. 2의 멱승을 하니 조금 이상할 수 있지만, 이진수 표현법이 기초가 됩니다. 홀수가 주어졌다고 하죠. 예를 들면 9가 주어졌습니다. 8 + 1 4 + 4 + 1 4 + 2 + 2 +.. 2023. 4. 29. [C/C++] 백준 #2302 극장 좌석(동적 계획법) #2302 극장 좌석 문제는 수학적인 원리를 이해하면 풀기 편합니다. 문제의 링크입니다. https://www.acmicpc.net/problem/2302 2302번: 극장 좌석 주어진 조건을 만족하면서 사람들이 좌석에 앉을 수 있는 방법의 가짓수를 출력한다. 방법의 가짓수는 2,000,000,000을 넘지 않는다. (2,000,000,000 < 231-1) www.acmicpc.net 극장 좌석은 일렬로 최대 40개까지 있을 수 있습니다. 이 중 몇개의 좌석은 이미 고정석으로 채워져 있을 때, 1부터 N까지의 숫자를 채우는 경우의 수를 구하는 문제입니다. 단, 모든 숫자는 자신의 자리 번호와 그 옆자리로 이동을 할 수 있지만, 고정석으로는 이동할 수 없습니다. 극장 자리는 아래와 같이 표시될 수 있습니.. 2023. 4. 20. [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. 이전 1 2 3 4 다음 728x90
