Study-Till-Death · realain · May 8, 2025 · DGJSKIM · May 12, 2025 · DGJSKIM
diff --git a/src/main/java/com/example/algorithmstudy/week19/MyAnswer055.java b/src/main/java/com/example/algorithmstudy/week19/MyAnswer055.java
@@ -0,0 +1,32 @@
+package com.example.algorithmstudy.week19;
+import java.io.BufferedReader;
+import java.io.IOException;
+import java.io.InputStreamReader;
+import java.util.*;
+
+//백준 2579번 계단 오르기
+public class MyAnswer055 {
+    public static void main(String[] args) throws IOException {
+        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
+        int stairCount = Integer.parseInt(br.readLine());
+        int[] stairScore = new int[stairCount + 1];
+        int[] dp = new int[stairCount + 1];
+
+        for (int i = 1; i <= stairCount; i++) {
+            stairScore[i] = Integer.parseInt(br.readLine());
+        }
+
+        dp[0] = 0;
+        dp[1] = stairScore[1];
+
+        if(stairCount >= 2){
+            dp[2] = stairScore[1] + stairScore[2];
+        }
+
+        for (int i = 3; i <= stairCount; i++) {
+            dp[i] = Math.max(dp[i - 2], dp[i - 3] + stairScore[i - 1]) + stairScore[i];
+        }
+
+        System.out.println(dp[stairCount]);
+    }
+}
diff --git a/src/main/java/com/example/algorithmstudy/week19/MyAnswer056.java b/src/main/java/com/example/algorithmstudy/week19/MyAnswer056.java
@@ -0,0 +1,36 @@
+package com.example.algorithmstudy.week19;
+import java.io.BufferedReader;
+import java.io.IOException;
+import java.io.InputStreamReader;
+import java.util.*;
+
+//백준 1994번 등차수열
+public class MyAnswer056 {
+    public static void main(String[] args) throws IOException {
+        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
+        int numCount = Integer.parseInt(br.readLine());
+        int[] numArr = new int[numCount];
+
+        for (int i = 0; i < numCount; i++) {
+            numArr[i] = Integer.parseInt(br.readLine());
+        }
+
+        Arrays.sort(numArr);
+
+        int maxCount = 1;
+
+        Map<Integer, Map<Integer, Integer>> dp = new HashMap<>();
+
+        for (int i = 0; i < numCount; i++) {
+            dp.put(i, new HashMap<>());
+            for (int j = 0; j < i; j++) {
+                int diff = numArr[i] - numArr[j];
+                int len = dp.get(j).getOrDefault(diff, 1) + 1;
+                dp.get(i).put(diff, len);
+                maxCount = Math.max(maxCount, len);
+            }
+        }
+
+        System.out.println(maxCount);
+    }
+}
diff --git a/src/main/java/com/example/algorithmstudy/week19/MyAnswer057.java b/src/main/java/com/example/algorithmstudy/week19/MyAnswer057.java
@@ -0,0 +1,43 @@
+package com.example.algorithmstudy.week19;
+import java.io.BufferedReader;
+import java.io.IOException;
+import java.io.InputStreamReader;
+import java.util.*;
+
+//백준 1695번 팰린드롬 만들기
+public class MyAnswer057 {
+    static int numCount;
+    static int[] numArr;
+    static int[][] dp;
+    public static void main(String[] args) throws IOException {
+        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
+        numCount = Integer.parseInt(br.readLine());
+        numArr = new int[numCount];
+        dp = new int[numCount][numCount];
+        for (int[] nums : dp) {
+            Arrays.fill(nums, -1);
+        }
+
+        StringTokenizer st = new StringTokenizer(br.readLine());
+        for (int i = 0; i < numCount; i++) {
+            numArr[i] = Integer.parseInt(st.nextToken());
+        }
+
+        int left = 0;
+        int right = numCount - 1;
+        System.out.println(checkPalindrome(left, right));
+    }
+    static int checkPalindrome (int left, int right) {
+        if(left > right) return 0;
+
+        if(dp[left][right] != -1) return dp[left][right];
+
+        if(numArr[left] == numArr[right]) {
+            dp[left][right] = checkPalindrome(left + 1, right-1);
+        }else{
+            dp[left][right] = Math.min(checkPalindrome(left + 1, right) + 1, checkPalindrome(left, right-1) + 1);
+        }
+
+        return dp[left][right];
+    }
+}