컴퓨터하는 kimmessi

https://www.acmicpc.net/problem/17404 17404번: RGB거리 2 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net 문제 해결 알고리즘 처음 집의 색을 정해놓고 시작한다. 이때, 색칠할 색이 아닌 색은 최댓값으로 설정해두고 다이나믹 프로그래밍을 해준다. 소스 코드 #include #include using namespace std; int arr[1002][3]; int dp[1002][3]; int main(){ int N; cin >> N; int result = 1000 * 1..

동적계획 알고리즘이란? 동적계획은 분할한 입력사례를 재귀 호출해 답을 얻고, 그 보다 작은 입력사례의 답을 먼저 구해 저장해놓고, 필요하면 꺼내 쓰는 알고리즘이다. 분할정복과는 달리 상향식(bottom-up) 접근 방법이다. 동적계획 알고리즘의 개발단계는 다음과 같다. 1. 문제의 입력사례에 대해서 해답을 계산하는 재귀 관계식을 세운다. 2. 작은 입력사례부터 먼저 해결하는 상향식 방법으로 전체 입력사례에 대한 해답을 구한다. 이항계수 구하기 이항계수 (binomial coefficient)는 다음과 같다. $$\left(\begin{array}{c}n\\ k\end{array}\right) = \frac{n!}{k!(n-k)!} \;\; \mathrm{for} \;\;0 \leq k \leq n$$ 위..