다이나믹 프로그래밍2 [백준] 1351번 - 무한 수열 [Java] https://www.acmicpc.net/problem/1351 1. 아이디어 Top-Down 방식의 다이나믹 프로그래밍과 HashMap을 통한 메모이제이션으로 해결할 수 있다.2. 문제풀이 수열의 특정 원소를 구하기 위해서 수열의 다른 두 원소의 합을 구해야 한다. 다른 두 원소도 역시 또 다른 두 원소의 합으로 이루어져 있고 해당 과정이 재귀적이므로 깊이 우선 탐색을 통해 구할 수 있다. 다만 이 과정에서 계산의 중복을 줄이기 위해 메모이제이션이 필요하고 수열의 길이가 int형 범위를 넘어갈 수 있어서 배열 대신 HashMap을 이용해서 메모이제이션을 했다.3. 코드 import java.io.*;import java.util.*;public class Main { private static.. 2024. 12. 23. [백준] 9625번 - BABBA [Java] https://www.acmicpc.net/problem/9625 1. 아이디어 K번 눌렀을 때 A와 B의 개수는 다이나믹 프로그래밍을 활용하면 구할 수 있다.2. 문제풀이 버튼을 눌렀을 때, B는 BA로 바뀌고, A는 B로 바뀐다.이를 식으로 표현하면 버튼을 n번 눌렀을 때 A와 B의 개수를 A(n), B(n)이라고 하면 A(n) = B(n-1), B(n) = B(n-1) + A(n-1) 이 된다.최초 화면에는 A가 표시되고 있고, 점화식이 나왔으니 다이나믹 프로그래밍으로 풀면 된다.3. 코드 import java.io.*;public class Main { public static void main(String[] args) throws IOException { BufferedR.. 2024. 12. 12. 이전 1 다음
