본문 바로가기

Algorithm22

백준 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.
백준 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.
백준 11053번 가장 긴 증가하는 부분 수열 주어진 수열에서 가장 길게 증가하는 부분 수열의 길이를 구하는 문제다. 수열에 주어진 각 숫자의 관점에서 최대 길이를 구해보면 다음과 같다. 1. 전체 수열이 A = {10} 으로 주어진 경우 최대 길이는 L = { 1} 이다. 2. 전체 수열이 A = {10, 20} 으로 주어진 경우 최대 길이는 L = { 1, 2} 이다. 3. 전체 수열이 A = {10, 20, 10} 으로 주어진 경우 최대 길이는 L = { 1, 2, 1} 이다. 4. 전체 수열이 A = {10, 20, 10, 30} 으로 주어진 경우 최대 길이는 L = { 1, 2, 1, 3} 이다. 5. 전체 수열이 A = {10, 20, 10, 30, 20} 으로 주어진 경우 최대 길이는 L = { 1, 2, 1, 3, 2} 이다. 6. 전.. 2023. 3. 15.

티스토리툴바