dynamic programming27 [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, ...과 같이 2k으로 표현되는 수)의 합으로 표시하는 경우의 수를 구하는 것입니다. 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. [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개가 있다면, 우리는 동적 계획법의 변수 dn,k를 정의하도록 합니다. n개의 동전을 가지고 k 금액을 만드는 경우의 수로 정의토록 합니다. 이렇게 하면 다음과 갈은.. 2023. 4. 20. [C/C++] 백준 #2225 합분해(동적 계획법) #2225 합분해 문제는 경우의 수를 찾는 문제입니다. 경우의 수를 찾는 문제들의 특성은 동적 계획법하고 상당히 잘 맞습니다. 문제는 동적 계획법을 어떻게 구성할 것인가죠. 그리고 꽤 많은 경우 간단하게 한번에 계산할 수 있는 경우의 수를 찾을 수도 있습니다. 물론 그것이 계승(factorial) 형태로 나오면 큰 의미도 없습니다. 문제의 링크입니다. https://www.acmicpc.net/problem/2225 2225번: 합분해 첫째 줄에 답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 문제의 요구사항은 간단합니다. 0부터 N까지의 수중에 K개를 뽑아서 합이 N을 만드는 경우의 수입니다. 중복된 수도 허용하고, 더하는 순서가 다르면 서로 다른 경우로 봅니다... 2023. 4. 17. 이전 1 2 3 4 5 다음 728x90
