My Dev Blog

public class Solution {

	// 이동하기 - DP 11048번
	
	static int n = 3;
	static int m = 4;
	static int[][] arr = {{1, 2, 3, 4}, {0, 0, 0, 5}, {9, 8, 7, 6}};
	static int[] dy = {1, 1, 0};
	static int[] dx = {0, 1, 1};
	static int[][] dp = new int[n][m];
	
	public static void dfs(int a, int b) {
		
		for (int i = 0; i < 3; i++) {
			int ny = a + dy[i];
			int nx = b + dx[i];
			
			if (ny > n - 1 || nx > m - 1) {
				continue;
			}
			
			dp[ny][nx] = Math.max(dp[ny][nx], arr[ny][nx] + dp[a][b]);
			dfs(ny, nx); // 24, 25라인 순서 잘 생각하자 dfs는 한 번 들어가면 그대로 쭉 들어가
		}
	}
	
	public static void dynamicProgramming() {
		dp[0][0] = arr[0][0];
		dfs(0,0);
		
		for (int i = 0; i < dp.length; i++) {
			
			for (int j = 0; j < dp[i].length; j++) {
				System.out.print(dp[i][j] + " ");
			}
			System.out.println();
		}
	}

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		// (1,1) 좌상단에서 (N,M) 우하단까지 사탕 최대로 얻기
		dynamicProgramming();
	}
}

백준 DP 11048번 이동하기

import java.util.*;

public class Solution {

	// 보물 - Greedy 1026번
	
	public static int minVal(int n, int[] arrA, int[] arrB) {
		
		int[] arrTempA = arrA;
		
		Integer[] tempB = Arrays.stream(arrB).boxed().toArray(Integer[]::new);
		
		Arrays.sort(tempB, Collections.reverseOrder());
		
		int[] arrTempB = Arrays.stream(tempB).mapToInt(Integer::intValue).toArray();
		
		Arrays.sort(arrTempA);
		
		int numVal = 0;
		
//		for (int i = 0; i < arrTempA.length; i++) {
//			System.out.print(arrTempA[i]);
//		}
//		
//		for (int i = 0; i < arrTempB.length; i++) {
//			System.out.print(arrTempB[i]);
//		}
		
		for (int i = 0; i < n; i++) {
			numVal += (arrTempA[i] * arrTempB[i]);
		}
		
		return numVal;
	}

	public static void main(String[] args) {
		// TODO Auto-generated method stub
//		5
//		1 1 1 6 0
//		2 7 8 3 1
		// 답 18
//		int n = 5;
//		int[] arrA = {1, 1, 1, 6, 0};
//		int[] arrB = {2, 7, 8, 3, 1};
		
//		3
//		1 1 3
//		10 30 20
		// 답 80
		
		int n = 3;
		int[] arrA = {1, 1, 3};
		int[] arrB = {10, 30, 20};
		
		System.out.println(minVal(n, arrA, arrB));
	}
}

백준 Greedy 1026번 보물