-

https://www.acmicpc.net/problem/1149 1149번: RGB거리 RGB거리에 사는 사람들은 집을 빨강, 초록, 파랑중에 하나로 칠하려고 한다. 또한, 그들은 모든 이웃은 같은 색으로 칠할 수 없다는 규칙도 정했다. 집 i의 이웃은 집 i-1과 집 i+1이고, 첫 집과 마지막 집은 이웃이 아니다. 각 집을 빨강으로 칠할 때 드는 비용, 초록으로 칠할 때 드는 비용, 파랑으로 드는 비용이 주어질 때, 모든 집을 칠하는 비용의 최솟값을 구하는 프로그램을 작성하시오. www.acmicpc.net 백준 DP 연습문제다. 입력받은 각 위치의 RGB값을 갖고 이전에 합산해둔 (메모이제이션) 최소 RGB 비용을 비교해 더 작은 비용값에 더해주며 최종 N의 자리까지 가면된다. N의 자리까지 가면..

https://www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 백준 DP 연습 문제다. DP는 크게 상향식, 하향식으로 나뉠 수 있는데, 이 문제는 상향식으로 풀었다. 즉, 초기값을 낮은곳에 잡고 이를 활용해 목적숫자로 커지며 답을 갱신하는 구조다. 작은 답이 큰 답의 도출에 이용되는 DP. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 #include #include #define maxlen 1000000+1 #define INF 987654321 usin..