0411

tykim94 · web-flow · commit 3dbd45003d09 · 2022-04-11T22:02:39.000+09:00
diff --git a/ProblemSolving/0210/0407스터디/Main_11066_파일_합치기_김태윤.java b/ProblemSolving/0210/0407스터디/Main_11066_파일_합치기_김태윤.java
@@ -0,0 +1,57 @@
+package algo_ex;
+
+import java.io.BufferedReader;
+import java.io.IOException;
+import java.io.InputStreamReader;
+import java.util.StringTokenizer;
+
+public class Main_11066_파일_합치기_김태윤 {
+
+	public static void main(String[] args) throws IOException {
+		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
+		StringTokenizer st = null;
+
+		int T = Integer.parseInt(br.readLine());
+
+		for (int t = 1; t <= T; t++) {
+			int K = Integer.parseInt(br.readLine());
+
+			int[][] dp = new int[K + 1][K + 1];
+			st = new StringTokenizer(br.readLine());
+			for (int i = 1; i <= K; i++) {
+				dp[i][i] = Integer.parseInt(st.nextToken());
+			}
+
+			int[] sum = new int[K+1];
+			
+			sum[1] = dp[1][1];
+			for(int i = 2; i<=K; i++) {
+				sum[i] = sum[i-1] + dp[i][i];
+			}
+			
+			
+			// 1칸씩, 2칸씩,, -> 1부터 시작, 2부터 시작 -> 가르기는 12 면 1<=k<2
+
+			for (int i = 1; i < K; i++) { // 사이 간격, [1][2] 이면 1
+				for (int j = 1; j <= K - i; j++) { // 시작점, [3(j)][4] 가 마지막이도록
+					for (int k = j; k < i + j; k++) { //중간지
+						System.out.println(i+" "+j+" "+k+"///"+"["+j+","+(j+i)+"]");
+						if (dp[j][j + i] == 0)
+							dp[j][j + i] = dp[j][k] + dp[k + 1][j + i];
+						dp[j][j + i] = Math.min(dp[j][j + i], dp[j][k] + dp[k + 1][j + i]);
+					}
+					if(i==1)
+						continue;
+					System.out.println(dp[j][j+i]);
+					dp[j][j+i] += (sum[j+i] - sum[j-1]);
+					System.out.println(dp[j][j+i]);
+					System.out.println();
+				}
+			}
+			
+			System.out.println(dp[1][K]);
+		}
+
+	}
+
+}
diff --git a/ProblemSolving/0210/0407스터디/Main_프로그래머스_도둑질_김태윤.java b/ProblemSolving/0210/0407스터디/Main_프로그래머스_도둑질_김태윤.java
@@ -0,0 +1,43 @@
+package algo_ex;
+
+public class Main_프로그래머스_도둑질_김태윤 {
+
+	static class Solution {
+		public int solution(int[] money) {
+			int answer = 0;
+			
+			if(money.length == 3)
+				return Math.max(money[0], Math.max(money[1], money[2]));
+			
+			//첫 집 턴다
+			int[] dp = new int[money.length];
+			dp[0] = money[0];
+			dp[1] = money[1];
+			dp[2] = money[0]+money[2];
+			for(int i = 3; i<money.length-1; i++) {
+				dp[i] = Math.max(dp[i-3] + money[i], dp[i-2] + money[i]);
+			}
+			answer = Math.max(dp[money.length-2], dp[money.length-3]);
+			
+			//첫 집 안 턴다
+			dp = new int[money.length];
+			dp[1] = money[1];
+			dp[2] = money[2];
+
+			for(int i = 3; i<money.length; i++) {
+				dp[i] = Math.max(dp[i-3] + money[i], dp[i-2] + money[i]);
+			}
+			answer = Math.max(answer, Math.max(dp[money.length-1], dp[money.length-2]));
+			
+			return answer;
+		}
+	}
+
+	public static void main(String[] args) {
+		Solution sss = new Solution();
+
+		int[] money = { 1, 2, 3, 1 };
+		System.out.println(sss.solution(money));
+	}
+
+}
