Dev.baelanche

dp 배열에 사탕의 최대값을 저장하면서 풀면된다. 1 2 3 4 0 0 0 5 9 8 7 6 오른쪽, 아래, 대각선으로 이동하므로 가장자리의 줄은 더해서 채워준다. 1 3 6 10 1 0 0 5 10 8 7 6 나머지 칸들은 [i-1][j-1], [i-1][j], [i][j-1] 중 최대값을 저장한다. 1 3 6 10 1 3 6 15 10 18 25 31 public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int m = sc.nextInt(); int a[][] = new int[n][m]; int dp[][] = new int[n][m]; f..

예제로 풀이해보겠다. a[0] a[1] a[2] a[3] a[4] a[5] 점수 10 20 15 25 10 20 점수 배열이다. a[0] a[1] a[2] a[3] a[4] a[5] 첫번째 경우 10 20 15 25 10 20 두번째 경우 10 20 15 25 10 20 마지막 계단은 반드시 밟아야 하므로 뒤에서 되돌아오는 식으로 점화식을 구현해야 한다. dp[5] = dp[2] + a[4] + a[5]; dp[5] = dp[3] + a[5]; 중 큰 값을 선택한다. 두번째 경우에서 a[1] 을 썼는지 a[2] 를 썼는지 확인할 수 없으므로 dp[3]만 사용한다. 식으로 나타내면 dp[i] = max(dp[i-3] + a[i-1] + a[i], dp[i-2] + a[i]); 가 되겠다. 이런식으로 구현하..

간단한 dp 문제이다. 7 3 8 8 1 0 2 7 4 4 4 5 2 6 5 아래 인덱스는 위에 인접해 있는 인덱스 중 큰것을 골라 더해간다. 7 3+7 8+7 8+3+7 1+8+7 0+8+7 2+8+3+7 7+8+3+7 4+1+8+7 4+1+8+7 4+2+8+3+7 5+7+8+3+7 2+7+8+3+7 6+4+1+8+7 5+4+1+8+7 dp[i][j] = max(dp[i-1][j-1], dp[i-1][j]) + a[i][j]; 점화식은 위와 같다. dp[i][0] 일때는 -1의 인덱스로 접근할 수 있으므로 이것만 유의하면 된다. public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); ..

예제의 값으로 풀이 방법을 서술해보겠다. R G B dp[0][i] = a[0][i] 26 40 83 dp 배열의 첫번째 인덱스에는 입력받은 값을 받는다. R G B dp[0][i] 26 40 83 dp[1][i] 49 + 40 60 + 26 57 + 26 색상은 연속으로 칠할 수 없으므로 다른 색상 중 최소값을 받아 더한다. R G B dp[0][i] 26 40 83 dp[1][i] 49 + 40 60 + 26 57 + 26 dp[2][i] 13 + 60 + 26 89 + 57 + 26 99 + 60 + 26 마찬가지로 채워준다. dp[i][0] = min(dp[i-1][1], dp[i-1][2]) + a[i][0]; dp[i][1] = min(dp[i-1][0], dp[i-1][2]) + a[i][1..

입력한 수 n 에 대하여 n번째 피보나치 수열을 구하면 된다. 점화식은 문제에 나와있는 식대로 하면되고 입력의 최대값이 t

가장 적은 횟수로 순서대로 세우려면 전체 아이의 수 - (가장 큰 증가 수열의 길이) 를 하면된다. 가장 큰 증가 수열의 길이를 구하는 법은 여기에 있다. public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int c[] = new int[n]; int dp[] = new int[n]; for(int i=0; i

가장 긴 증가하는 부분 수열, 가장 긴 감소하는 부분 수열과 로직이 똑같은 문제이다. 수열의 길이가 아닌 각 수열의 합을 dp 배열에 담으면 된다. public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int a[] = new int[n]; int dp[] = new int[n]; for(int i=0; i

가장 긴 감소하는 부분 수열을 먼저 풀고 풀었다. 수열의 수에 대한 크기 비교만 거꾸로 하면 된다. public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int a[] = new int[n]; int dp[] = new int[n]; for(int i=0; i