Algorithm

[백준 알고리즘] 14889번 스타트와 링크 (JAVA)

주의 사항 해당 문제는 두가지 유형으로 풀이가 가능하다. DP 완전 탐색 : n은 11보다 작기에 시간복잡도는 O(n!) = O(10!) = 3,628,800 (대략 40만) < 100,000,000 (1초) 이다. 코드 블럭 DP (다이나믹 프로그래밍) package boj400; import java.util.ArrayList; import java.util.Scanner; public class boj_9095 { public static void main(String[] args) { Scanner scanner = new Scanner(System.in); int n = scanner.nextInt(); ArrayList list = new ArrayList(); for (int i = 0; i..

[백준 알고리즘] 14889번 스타트와 링크 (JAVA)

주의 사항 1번 2번 3번을 뽑는것과 3번 1번 2번을 뽑는것은 같다. 즉, 해당 문제는 순열이 아닌 조합을 사용해서 풀어야한다. 코드 블럭 package boj530; import java.util.ArrayList; import java.util.Scanner; public class boj_14889 { static int min = Integer.MAX_VALUE; public static void main(String[] args) { Scanner scanner = new Scanner(System.in); int n = scanner.nextInt(); int[][] matrix = new int[n][n]; for (int i = 0; i < n; i++) { for (int j = 0; ..

[백준 알고리즘] 2156번 포도주 시식 (JAVA)

주의 사항 포도주를 마시는 경우의 수가 3가지 이기 때문에 i = 1, i = 2, i = 3을 계산 후 i = 4 일때부터 시작해야한다. OOX, OXO, XOO (총 3가지) 코드 블럭 package boj401; import java.util.Scanner; public class boj_2156 { public static void main(String[] args) { Scanner scanner = new Scanner(System.in); int n = scanner.nextInt(); int[] arr = new int[n]; for (int i = 0; i < n; i++) { arr[i] = scanner.nextInt(); } int[] dp = new int[n]; if (n < 3..

[백준 알고리즘] 1932번 정수 삼각형 (JAVA)

주의 사항 첫번째와 마지막번째 그리고, 그 외의 순서에서의 점화식이 다르다. i = 첫번째, i = 마지막, i = 두번째 ~ 마지막 -1 까지의 점화식을 세워 풀자. i = 첫번째 -> dp[i][j] = dp[i-1][j] + matrix[i][j] i = 두번째 ~ 마지막 - 1 -> dp[i][j] = dp[i-1][j-1] + matrix[i][j] i = 마지막 -> Math.max(dp[i-1][j-1], dp[i-1][j]) + matrix[i][j] 왼쪽 대각 위, 오른쪽 대각 위 중 큰 값을 넣어줘야 한다. 코드 블럭 package boj401; import java.util.Scanner; public class boj_1932 { public static void main(Stri..