본문 바로가기

전체 글62

백준 1149번 RGB거리 주어진 규칙에 따라 모든 집을 색칠할 때 드는 최소한의 비용을 구하는 문제다. 단순히 각 집집마다 가장 저렴한 색상을 사용한다면 최소한의 비용을 구할 수 있다고 생각할 수 있지만, 규칙에 따른다면 불가능해진다. cost[N][R] : N번째 집을 Red로 칠할 때 드는 비용이라고 하고, 각 집의 최소 비용을 수식으로 정리해보면 다음과 같다. N 번째 집 Red Green Blue 1 cost[1][R] cost[1][G] cost[1][B] 2 cost[2][R] + min(cost[1][G], cost[1][B]) cost[2][G] + min(cost[1][R], cost[1][B]) cost[2][B] + min(cost[1][R], cost[1][G]) 3 cost[3][R] + min(cost[.. 2023. 3. 16.
백준 9461번 파도반수열 규칙에 따라 나선 모양으로 놓여진 정삼각형들 중 N번째 놓여진 정삼각형의 한 변의 길이를 구하는 문제다. N번째 정삼각형의 한 변의 길이를 나열한다면 규칙을 쉽게 찾을 수 있다. P(1) = 1 P(2) = 1 P(3) = 1 P(4) = 2 = P(2) + P(1) P(5) = 2 = P(3) + P(2) P(6) = 3 = P(4) + P(3) P(7) = 4 = P(5) + P(4) P(8) = 5 = P(6) + P(5) P(9) = 7 = P(7) + P(6) P(10) = 9 = P(8) + P(7) ... P(N) = P(N-2) + P(N-3) import java.util.Scanner; public class Main { static long dp = new long[101]; publ.. 2023. 3. 16.
자바 - 2차원 배열 정렬 (오름차순, 내림차순, 다중 조건) 자바의 2차원 배열을 Arrays.sort() 를 통해 곧바로 정렬하려고 하면 java.lang.ClassCastException: I cannot be cast to java.lang.Comparable 오류가 발생한다. 오류 문구와 같이 비교 기준이 없어 캐스팅에 실패하기 때문이다. 예시와 같이 Comparable, Comparator 인터페이스를 구현하여 정렬 기준을 추가해줘야 한다. 1. 오름차순, 내림차순 정렬 int[][] arr = new int[][]{{1, -1}, {2, 2}, {3, 3}, {1, 2}, {0, 4}} Arrays.sort(arr, new Comparator() { @Override public int compare(int[] o1, int[] o2) { return .. 2023. 3. 15.
백준 9184번 신나는 함수 실행 주어진 재귀함수를 실제로 구현하는 문제다. 동적프로그래밍을 활용할 경우, 값을 저장할 배열(DP 라고 하겠다)의 사이즈를 고민해볼 필요가 있다. 문제의 제한 사항에서 a, b, c의 범위가 주어졌지만, 주어진 재귀함수의 첫 번째와 두 번째 조건 if a 20, then w(a, b, c) returns: w(20, 20, 20) 에 의해 DP의 사이즈는 [21][21][21] 로 선언할 수 있다. import java.util.Scanner; public class Main { static int[][][] dp = new int[21][21][21]; public static void main(String[] args) { Scanner in = new Scanner(System.in); StringB.. 2023. 3. 15.