본문 바로가기

Dynamic Programming2

[백준] 2629. 양팔 저울 문제 풀이 오랜만에 푸는 DP문제였다. 먼저 추를 넣었을 때 만들 수 있는 추의 무게를 저장하기 위한 Cache배열을 유지했다. 이 때 해당 추에 대해 만들 수 있는 경우 수는 다음과 같다. 현재 추만 넣은 경우 이전 단계에서 만들었던 무게를 그대로 사용하는 경우 이전 단계에서 만들었던 무게에 현재 추를 더하는 경우 이전 단계에서 만들었던 무게에 현재 추를 빼는 경우 (물체쪽에 추를 놓는 경우) 최종적으로 마지막 추를 넣었을 때 가능한 무게를 구할 수 있다. import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; public class Main { // Input 받기 위한 Buffered Re.. 2021. 4. 1.

[백준] 9251. LCS 문제 풀이 하루종일 이 문제만 붙들고 있었던 것 같다. 처음 시도했던 방법은 일차원 배열을 통해 메모이제이션을 수행하고자 했다. 하지만 일차원 배열을 사용하는 경우에는 같은 문자가 여러번 등장할 경우에 대해서 잘못된 최대값을 얻는 경우가 발생한다. import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; public class Main { static BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); static int[][] cache; public static void main(String[] args) thro.. 2021. 2. 10.

티스토리툴바