반응형 동적계획법8 [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. [C/C++] 백준 #2133 타일 채우기(동적 계획법) #2133 타일 채우기 문제는 동적 계획법을 이용해서 풀 수가 있습니다. 하지만 원리만 알면 조금 더 쉬운 방법으로도 해결할 수가 있습니다. https://www.acmicpc.net/problem/2133 2133번: 타일 채우기 3×N 크기의 벽을 2×1, 1×2 크기의 타일로 채우는 경우의 수를 구해보자. www.acmicpc.net 문제는 3xn 공간을 2x1 타일로 채우는 경우의 수를 구하라는 문제입니다. 아주 간단하지만 n이 홀수인 경우에는 채울 수 있는 방법이 없습니다. n이 짝수인 경우에만 채울 수 있는 경우가 발생하죠. 저는 동적 프로그래밍을 하기 위해서 다음과 같은 경우를 생각했습니다. 마지막 칸에 나올 수 있는 패턴들입니다. 마지막 칸의 패턴은 아무것도 없는 상태, 맨 위에만 한칸 채.. 2023. 4. 8. [C/C++] 백준 #1563 개근상(동적계획법) 개근상 문제는 동적계획법을 이용하는 문제이지만, 조건이 조금 까다롭습니다. 연속결석이 3번 이어지면 안 되기 때문에 당연히 동적 계획법을 사용하는 것이 바람직합니다. 그런데 지각 정보도 있으니까요. 출석은 O, 결석은 A, 지각은 L로 표현했을 때, 5일간 출석 정보를 가지고 개근상을 따진다면, OOOOO와 같은 경우는 당연히 되겠죠. AALAL 과 같이 지각을 두번 이상한 경우에는 개근상을 받지 못합니다. AALAA와 같이 4번 결석에 1번 지각의 경우는 개근상을 받겠죠. https://www.acmicpc.net/problem/1563 1563번: 개근상 백준중학교에서는 학기가 끝날 무렵에 출결사항을 보고 개근상을 줄 것인지 말 것인지 결정한다. 이 학교는 이상해서 학생들이 학교를 너무 자주 빠지기 .. 2022. 9. 6. [C/C++] 백준 #1562 계단 수(동적 계획법) 계단 수는 1232나 34545와 같이 인접한 자리수의 숫자 차이가 1인 수를 말합니다. 이러한 자리의 수의 경우의 수를 구하는 것은 크게 어렵지는 않을겁니다. 그런데, 이번문제는 0부터 9까지의 모든 숫자가 포함되어야 합니다. https://www.acmicpc.net/problem/1562 1562번: 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 여기서 0부터 9까지 모든 숫자가 다 있어야 한다는 것이죠. 동적계획법을 이용하더래도 최소수, 최대수, 그리고 마지막수가 있어야 합니다. 즉, 123234323 과 같은 숫자는 최소수 1, 최대수 4, 그리고 마지막 수 3이 됩니다. 그러면 이 다음에 붙일 수 있는 수는 2 또는 4가 됩니다. .. 2022. 9. 6. #1521 랜덤 소트(dynamic programming) 이번 문제는 꽤 재미있는 주제입니다. 인공지능 마르코프 체인을 이야기하다보면, 기대값을 계산하는 부분이 있습니다. 이 부분을 잘 활용하고, 그리고 잦은 중복 호출이 발생하니 동적 계획법도 이용해야 합니다. 문제는 아래와 같습니다. https://www.acmicpc.net/problem/1521 1521번: 랜덤 소트 첫째 줄에 순열의 크기 N이 주어진다. 둘째 줄에 순열에 들어있는 수 N개가 주어진다. 이 수는 모두 1보다 크거나 같고, N보나 작거나 같으며, 같은 수는 2번 이상 주어지지 않는다. 또, N은 8보다 www.acmicpc.net 마르코프 프로세스에 의하면 우리가 현재 상태(\(S_c\))의 기대값은 다음과 같이 구할 수 있습니다. \[ E(S_c) = \sum_{p} P_{c, p} \.. 2022. 8. 31. #1520 내리막 길 내리막 길 문제는 나올 수 있는 모든 경로의 개수를 구하는 프로그램입니다. 일반적으로 이렇게 경우의 수를 물어보는 문제는 동적 계획법(dynamic programming)을 이용하면 풀기 쉬워집니다. 문제는 다음과 같습니다. https://www.acmicpc.net/problem/1520 1520번: 내리막 길 여행을 떠난 세준이는 지도를 하나 구하였다. 이 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 한 칸은 한 지점을 나타내는데 각 칸에는 그 지점의 높이가 쓰여 있으 www.acmicpc.net 그러면 어떻게 하면 좋을까요? 상하좌우로 움직일 수 있으니, \((i, j)\)에서의 경우의 수 \(d_{i, j}\)는 주변의 값들의 합으로 나타낼 수 있습니다. \[ d_{i,.. 2022. 8. 29. 이전 1 2 다음 728x90
