RGB 거리

1. 소스 코드

백준 https://www.acmicpc.net/problem/1149 문제 정리. 완전 탐색으로 풀었을 때, 비교하나 잘 못해서 3일동안 뻘짓.

다행히 고마우신 분이 힌트를 주어서 해결. DP 문제라고 구지 분류하니까 너무 복잡하게 생각했는데 단순하게

생각하면 이해하기 어렵진 않았다.

완전 탐색 시에는 O(N^2)의 복잡도와 메모리는 문제에서 데이터 입력량만큼 늘어난다. 하지만 완전 탐색이 아닌 접근법으로 구현 시에는 복잡도는 O(N)으로 보이고 메모리는 데이터 입력량에 Constant이다.

[완전탐색]

#include <iostream> unsigned int data[1001][3]; unsigned int min = 0xFFFFFFFF; int n; void f(int c, int d, unsigned int v) { if (d == n) { if (min > v) { min = v; } return; } for (int i = 0; i < 3; i++) { if (i != c) { f(i, d + 1, v + data[d][i]); } } } int main() { std::cin >> n; for (int i = 0; i < n; i++) { std::cin >> data[i][0] >> data[i][1] >> data[i][2]; } f(-1, 0, 0); std::cout << min << std::endl; return 0; }

[일반적인 내 수준에서 풀이 시]

#include <iostream> int main() { int n; int a, b, c; int minA, minB, minC; int prevMinA = 0, prevMinB = 0, prevMinC = 0; std::cin >> n; for (int i = 0; i < n; i++) { std::cin >> a >> b >> c; minA = std::min(prevMinB, prevMinC) + a; minB = std::min(prevMinA, prevMinC) + b; minC = std::min(prevMinA, prevMinB) + c; prevMinA = minA; prevMinB = minB; prevMinC = minC; } std::cout << std::min(std::min(minA, minB), minC) << std::endl; return 0; }

2. 실행결과

두 개 백준 사이트에서 돌렸을 때, 잘 동작하였다.