BOJ 1149https://www.acmicpc.net/problem/1149 문제 이 문제는 선분위에 나열되어 있는 N개의 집을 R, G, B 색으로 정해진 규칙에 따라 도색하고, 그에 따른 도색 비용의 최솟값을 구하는 DP 문제입니다. 도색 규칙을 간단하게 살펴 보자면, 1번 집의 색 ≠ 2번집의 색N번 집의 색 ≠ N-1번 집의 색i(2 ≤ i ≤ N-1)번 집의 색 ≠ i-1번, i+1번 집의 색 결국 이 규칙은 모든 서로 이웃한 집끼리는 색이 달라야 한다는것을 알 수 있습니다. 여기서 중요한 점은 i번째 집을 칠할 때는 바로 이전 집(i-1)만 다른 색이면 충분하다는 것입니다. 왜냐하면 DP는 왼쪽 → 오른쪽으로 순서대로 집을 칠해 나가므로, 이미 i-1까지 규칙을 만족하도록 최적 비용으로 ..

BOJ 9465https://www.acmicpc.net/problem/9465 문제 스티커를 떼면 그 스티커의 십자방향의 스티커들은 앞으로 사용할 수 없다고 하고, 이 조건하에 땐 스티커들의 점수의 최댓값을 구하는 문제입니다. 입력첫째 줄에 테스트 케이스 T각 케이스의 첫째 줄에는 n (1 ≤ n ≤ 100,000)다음 두줄에는 n개의 정수(0 ≤ 정수 ≤ 100) → 그 위치에 해당하는 스티커의 점수출력각 테스트 케이스 마다, 2n개의 스티커 중에서 두 변을 공유하지 않는 스티커 점수의 최댓값을 출력 풀이DP 배열 정의이 문제에서 DP 배열은 자동으로 상하좌우에 대한 스티커를 배제하기 위해서, i열에서 state에 따른 최대 점수로 생각했습니다.n이 몇으로 주어지든 배열은 2행 n열로 ..