Dynamic Programming2

• 

  [C++] 백준 - 전구 문제 2. 입출력 3. 문제 해설 문제를 읽어보면 최대 K가지의 서로 다른 색을 표현할 수 있는 전구들이 존재하고 이 전구 N개를 한 줄로 배치한다. 한 줄로 배치한다는 것은 고리 형태가 아닌 자신의 양 옆의 전구만이 자신에게 영향을 줄 수 있다는 뜻이다. 또한 임의의 전구를 하나 잡아 색을 바꾼다. 그런데 이 임의의 전구와 인접한 전구가 같은 색이라면 이 전구 또한 색상이 변한다. 그러면 이 문제는 최소 문제로 쪼갤 수 있다. 바로 옆의 전구가 변했을 때 색이 같다면 변하고 색이 다르다면 변하지 않는 것이다. 그러면 이 문제는 dp를 적용해 memoization 해 가면서 풀 수 있을 거 같다고 생각했다. 이 문제에서 제일 까다로운 점은 임의의 전구부터 시작할 수 있다는 점이다. 또한 dp를 이용하려면.. c++/알고리즘 2023. 1. 30.

• 

  [c++] 백준-제단 5626 문제 입력과 출력 사실 이 문제를 풀 때 DP를 이용해서 푸는 문제라는 것을 알고 있었기 때문에 쉽게 접근할 수 있었다. (물론 난이도 자체는 어렵다 매우) DP는 점화식을 세우면 끝나는 문제다. 문제를 파악해보면 다음과 같다. 문제 해설 우선 제단을 세울 수 있는 경우를 생각해보았다. x 가능 가능 x x 가능 가능 가능 가능 x 점화식은 대부분 memoization된 이전 상태에서 현재의 값을 찾아낼 수 있기에 두 가지의 경우만을 고려해보았다. 2층의 가능한 경우는 1층의 경우에 따라 가능할 수도 불가능할 수도 있다. 따라서 이는 현재 상태가 이전 관계에 영향을 받는 점화식으로 풀 수 있는 DP문제이다. 그렇다면 현재 상태는 이전 상태의 어떠한 영향을 받을까? 다음 세 가지 경우가 있을 수 있다. 현.. c++/알고리즘 2023. 1. 25.