RGB거리1 [C] 1149: RGB거리 전형적인 Dynamic Programming 문제인걸 알 수 있었는데 그 이유는 subproblem을 여러번 이용해야하기 때문에 이를 위해서 dp[]에 저장해서 이용해야했고 최솟값과 관련된 문제였기 때문이다. 이 문제는 i=1일때부터 하나하나씩 해보면 점화식을 구하는 것보다는 i=n일때부터 거꾸로 생각하는게 좀 더 떠올리는게 쉬웠던 것 같다. (2Xn 타일링2와 같이!) 그리고 빨강,초록,파랑 각각을 선택했을때 최선인 경우를 따로따로 저장하는 것이 각각 생각하지 않고 dp[i]일때 최선인 것을 저장하는 것보다 효율적이었는데 이는 똑같은 색깔을 두번 연속 선택하지 못한다면 그 다음에 최선인 경우를 빨리 찾기 위해서이다. #include int red[1001]; int green[1001]; int blu.. 2023. 7. 30. 이전 1 다음