본문 바로가기

전체 글149

[백준] JAVA 자바 : 스티커 (9465번) 어려운 줄 알았는데 막상 생각을 좀 해보니 생각보다 쉬웠던 문제다. 가로의 길이를 N으로 두고 1부터 올려가면서 점화식을 구하면 된다. N이 N+1이 될 때 가질 수 있는 최대 가치는, N에서 윗줄(아랫줄)을 선택했다면 N+1번째에는 아랫줄(윗줄)을 선택하는 것 혹은 N-1번째에서 큰 값중 N+1번째의 위아래를 더하는 값 중 하나로 결정된다. 솔직히 이것도 글로만 보면 이해가 안 돼서... 코드로 보고 이해하심 됩니다ㅋㅋ import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Sticker { public sta.. 2024. 1. 23.
[백준] JAVA 자바 : 오르막 수 (11057번) 오늘 근로하면서 오전 시간 내내 이것만 붙들고 있었는데... 진짜 한 3시간 정도 고민한 끝에 겨우겨우 점화식을 도출해서 풀 수 있었다... 난 아직 DP에 대해 전혀 알지 못하는 듯........ 여튼 자릿수를 N으로 놓고 1부터 차근차근 올려보면 dp[1] = 10; // 10 dp[2] = 55; // 10 + 9 + 8 + 7 + 6 + 5 + 4 + 3 + 2 + 1 dp[3] = 220; // 55 + 45 + 36 + 28 + 21 + 15 + 10 + 6 + 3 + 1 dp[4] = 715; // 220 + 165 + 120 + 84 + 56 + 35 + 20 + 10 + 4 + 1 ... 이렇게 된다. 즉 직전 수에서 이전 배열의 자릿수에 있는 수 만큼을 뺀 값을 더하면 된다. 나도 글로.. 2024. 1. 23.
[백준] JAVA 자바 : 동물원 (1309번) 어떻게 풀어야 할 지 참 난감한 문제였는데... 곰곰이 생각해서 겨우 풀 수 있었다. 간단히 얘기하자면, N-1번째에서 세로로 N번째 층을 더 올렸을 때의 경우의 수는 다음으로 구할 수 있다. N번째 층을 쌓지 않는 경우: N-1번째 층을 구하는 경우와 동일 N번째 층을 쌓는 경우 - N-1번째 층이 쌓여있다면 거기서 단순히 N번째 층이 정해진다. N번째 층을 쌓는 경우 - N-1번째 층이 쌓여있지 않다면 왼쪽과 오른쪽 중 하나를 고를 수 있으므로 x2 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Zo.. 2024. 1. 23.
[백준] 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.
반응형

티스토리툴바