PS/동적계획법3

• 

  [백준 with JAVA] 1149번 : RGB 거리 - DP 1149번: RGB거리 1149번: RGB거리 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net 문제 문제 접근 문제 조건을 보면 결국 i번째 집이 있다고 했을 때 color[i - 1] ≠ color[i] && color[i] ≠ color[i + 1] 이 성립하면 되는 문제입니다. 조건만 봐도 바로 점화식이 나와버리는 문제였습니다. 한 가지 더 생각을 하자면 마지막 선택한 집이 Red 일 경우 Green 일 경우 Blue 일 경우 로 3가지 구분 지어서 점화식을 만든 후에 마지막에 비교해주시면 되겠습니다. 나.. PS/동적계획법 2022. 8. 9.

• 

  [백준 with JAVA] 2579번 : 계단오르기 - DP 2579번: 계단 오르기 2579번: 계단 오르기 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점 www.acmicpc.net 문제 보기 DP 문제이기에 이 문제를 어떻게 세부 문제로 나눠서 점화식을 세울까 고민했습니다. 개인적으로 점화식을 세워서 문제를 맞추는데 성공했지만 다른 분들과 코드를 비교했을 때 내용이 달라 제 코드와 다른 분들의 코드를 비교해서 포스팅 하겠습니다. 1. 내 문제 접근법 문제를 보면 다음과 같은 조건들이 있습니다. 연속해서 세 칸을 올라가지 못한다. 저는 이 조건을 보고 계단에서 일정한 규칙으로 움직여야 함을 알 수 있었습니다. 한 칸 올라감을 1.. PS/동적계획법 2022. 8. 9.

• 

  [백준] 1915번 : 가장 큰 정사각형 - DP 1915번: 가장 큰 정사각형 1915번: 가장 큰 정사각형 첫째 줄에 n, m(1 ≤ n, m ≤ 1,000)이 주어진다. 다음 n개의 줄에는 m개의 숫자로 배열이 주어진다. www.acmicpc.net 너 DP 좀 치냐 ? 이번 문제는 DP 문제입니다. 문제 n×m의 0, 1로 된 배열이 있다. 이 배열에서 1로 된 가장 큰 정사각형의 크기를 구하는 프로그램을 작성하시오. 0100 0111 1110 0010 위와 같은 예제에서는 가운데의 2×2 배열이 가장 큰 정사각형이다. 문제 접근 배열을 순차적으로 돈다고 했을 때 이미 정사각형을 구한 부분도 다시 구하게 된다는 사실은 당연히 알 수 있습니다. 때문에 이 부분을 방지할 수 있는 방법이 필요합니다. 처음에 저는 한 좌표에서 right, rightDo.. PS/동적계획법 2022. 8. 6.