본문 바로가기

전체 글149

[백준] 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.
[백준] JAVA 자바 : 카드 구매하기 (11052번) N개의 카드를 구매하기 위해서는 price[N]의 가격과 dp[N-i] + dp[i] (i 2024. 1. 22.
[백준] JAVA 자바 : 1, 2, 3 더하기 (9095번) 사실 아직까지 DP 알고리즘 문제들은 대개 비슷한 유형이라서… 그냥 dp[] 배열에 이전 값들의 경우의 수를 저장해둔 다음 바텀탑이나 탑다운 방식으로 dp[] 배열을 완성해 나가면 된다. 나 같은 경우는 바텀탑이 편해서 바텀탑만 사용하는 중… 이 문제 같은 경우도 똑같이 해결할 수 있다! 그러나 최대 3까지 더할 수 있으므로 나는 초깃값을 3개 설정해 두고, for 반복문을 4부터 n까지 돌리게 작성했다. import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; public class Sum123 { public static int stoi(String str) { return Integer.pa.. 2024. 1. 22.
[백준] JAVA 자바 : 2×n 타일링 2 (11726번) 직전 문제인 2×n 타일링에서 추가할 수 있는 블럭의 개수가 하나 늘어난 케이스이다. 이건 2×n 타일링 문제를 이해하고 푸셨다면… 진짜 2분 안에 해결하실 수 있을 것 같다. 기존의 dp[i] = dp[i-1] + dp[i-2]라는 코드는 dp[i]에 1×2로 채우는 경우 + 2×1로 채우는 경우를 뜻했다. 그러나 2×1로 채우는 경우의 수는 2×2로 채우는 경우의 수와 똑같으므로… dp[i-2]를 더해줄 때 2배를 해서 더해주면 된다. import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; public class Tiling_2n_2 { public static int stoi(String .. 2024. 1. 22.
반응형

티스토리툴바