[c++] 백준 1149 RGB 거리
백준 단계별로 풀어보기 [동적계획법] RGB 거리 https://www.acmicpc.net/problem/1149 1149번: RGB거리 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net [풀이] n개의 집을 빨,초,파 중 하나로 칠해야 한다. 같은 색이 연속으로 반복되면 안될 때 모든 집을 칠하는 비용의 최솟값을 구하는 문제이다. 동적계획법으로 이 문제를 풀 때, 생각해야 할 것은 당장의 최솟값을 구해 더하는 것이 전체의 최솟값이 되지 않는다는 것이다. 예를 들어, 다음과 같이 3개의 집에 대해 빨,초,파 비..
[c++] 백준 2630 색종이 만들기
백준 단계별로 풀어보기 [분할 정복] 색종이 만들기 https://www.acmicpc.net/problem/2630 2630번: 색종이 만들기 첫째 줄에는 전체 종이의 한 변의 길이 N이 주어져 있다. N은 2, 4, 8, 16, 32, 64, 128 중 하나이다. 색종이의 각 가로줄의 정사각형칸들의 색이 윗줄부터 차례로 둘째 줄부터 마지막 줄까지 주어진다. www.acmicpc.net [풀이] 재귀호출을 위한 인자로 y의 시작 좌표, x의 시작 좌표, size(width==height)를 전달해준다. 처음 arr[y][x]와 비교하여 다른 색이 붙어있다면 왼쪽 위, 오른쪽 위, 왼쪽 아래, 오른쪽 아래로 나누어 재귀호출을 해준다. 모두 하얀색이었다면 white_color 수를 증가해주고, 모두 파란색..