자바77 [백준] JAVA 자바 : RGB거리 (1149번) N개의 집을 입력받으면, N개의 집 각각의 cost를 입력받아서 저장한다. 이 때, 당연히 코스트를 계산할 dp 배열도 선언해야 한다. dp배열은 마지막이 red(1), green(2), blue(3) 중 어디로 저장되는지도 저장해야 하므로 이차원 배열으로 선언한다. 그리고 dp배열을 red green blue 각각 계산한다. red(1)는 앞선 배열이 green(2)과 blue(3)으로 끝나는 경우에 r_cost를 더해서 계산하고, green(2)는 앞선 배열이 red(1)과 blue(3)으로 끝나는 경우에 g_cost를 더해서 계산하며, blue(3)는 앞선 배열이 red(1)과 green(2)으로 끝나는 경우에 b_cost를 더해서 계산한다. 그리고 계산된 배열의 N번째 요소들 중 가장 작은 값을 .. 2024. 1. 23. [백준] JAVA 자바 : 1, 2, 3 더하기 3 (15988번) 앞서 1, 2, 3 더하기 문제들과 큰 차이가 없는 문제다. 그런데 솔직히 이제와서 그 문제가 뭐였는지 기억도 안 나서 ㅋㅋ 그냥 다시 짰다. N은 1~1000000 사이의 수이므로 1000001까지의 long 배열을 만든 후 1, 2, 3을 더해서 만들 수 있는 모든 경우의 수를 다 저장한다. 그리고 for문을 돌면서 n을 입력받을 때마다 dp[n]을 출력하면 된다. import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Sum123_3 { static int MOD = 1000000009; public sta.. 2024. 1. 23. [백준] JAVA 자바 : 합분해 (2225번) 솔직히 연속합 전까지는 DP가 너무 쉬워서 물로만 느꼈었는데... 슬슬 골드 단계까지 오니까 굉장히 어려운 문제라는 걸 뼈저리게 느끼고 있다... N=1 K=1: 1 K=2: 01 10 K=3: 001 010 100 N=2 K=1: 2 // dp[2][1] K=2: 02 20 11 // dp[2][1] + dp[1][2] K=3: 002 020 200 110 101 011 // dp[2][2]+dp[1][3] N=3 K=1: 3 // dp[3][1] K=2: 03 30 12 21 // dp[3][1] + dp[2][2] K=3: 003 030 300 012 102 120 021 201 210 111 // dp[3][2] + dp[2][3] N=6 K=1: 6 K=2: 06 60 15 51 24 42 33.. 2024. 1. 23. [백준] JAVA 자바 : 연속합 (1912번) 연속합 부터 DP가 조금 어려워진 것 같다. DP의 기본은 '이전에 계산한 값을 이후 계산에서 사용하는 것'이다... 이 본분을 까먹지 말자. 즉 DP는 점화식을 잘 찾아내면 무조건 풀 수 있다. import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; public class ContinuousSum { public static int stoi(String str) { return Integer.parseInt(str); } public static void main(String[] args) throws IOException { Buf.. 2024. 1. 23. [백준] JAVA 자바 : 가장 긴 증가하는 부분 수열 4 (14002번) 다이나믹프로그래밍에서 처음 만난 골드 등급 문제… 이거 푸려고 몇 시간을 헤맸다… 분명 가장 긴 증가하는 부분 수열은 나쁘지 않게 풀렸는데 가장 긴 수열을 출력하는 부분이 상당히 오래 걸림… 나는 어떻게 풀었냐면 가장 길어지는 부분의 인덱스를 now라는 변수에 저장해 놓고, 가장 길어질 때마다 그 때의 인덱스로 now를 갱신했다. 그리고 외부 for문을 한 바퀴 돌 때마다 dp[now]와 현재의 dp[i]를 비교해서, dp[i]가 dp[now]보다 길다면 현재까지 가장 길었던 수열(sa[now])에 지금의 수 A[i]를 덧붙이고, 그렇지 않다면 sa[i]에는 A[i]부터 시작하는 새로운 수열을 담도록 했다. 나도 글로 쓰니까 무슨 말인지 제대로 이해가 안 되는데… 머릿속으로 그린 걸 글로 쓰는게 참 힘들.. 2024. 1. 23. [백준] JAVA 자바 : 카드 구매하기 2 (16194번) 사실 직전 문제인 에서 부등호 하나만 바꿔주면 해결되는 문제… 알고리즘 역시 모두 똑같아서… 따로 부연 설명은 필요 없을 듯. import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; public class BuyingCards2 { static int[] dp; static int[] price; public static int stoi(String str) { return Integer.parseInt(str); } public static void main(String[] args) throws IOException { Buffer.. 2024. 1. 23. 이전 1 ··· 3 4 5 6 7 8 9 ··· 13 다음 반응형
