다이나믹프로그래밍2 [백준 Silver 1] 1309 동물원 - Java 문제링크 : https://www.acmicpc.net/problem/1309 1309번: 동물원 첫째 줄에 우리의 크기 N(1≤N≤100,000)이 주어진다. www.acmicpc.net 접근 과정 : 2차원 배열(zoo[][])을 선언하고, 2칸 모두 사자가 없는 경우 / 왼쪽칸에 사자가 있는 경우 / 오른쪽칸에 사자가 있는 경우로 경우의 수를 더했다 즉, Bottom-Up 방식으로 DP를 구현하였다. 소스 코드 및 결과 : package BOJ; /* 동물원 */ import java.io.*; public class BOJ1309 { public static void main(String[] args) throws NumberFormatException, IOException { BufferedR.. 2021. 12. 23. [백준 Silver 2] 11722 가장 긴 감소하는 부분 수열 - Java 문제링크 : https://www.acmicpc.net/problem/11722 11722번: 가장 긴 감소하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 감소하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 30, 10, 20, 20, 10} 인 경우에 가장 긴 감소하는 부분 수열은 A = {10, 30, 10, 20, 20, 10} www.acmicpc.net 접근 과정 : 수열 A를 모두 입력 받은 후에, 감소 수열 체크 dp[] 는 해당 인덱스까지의 확인했을 때, 가장 긴 감소 수열의 크기를 의미 수열 A를 순회하면서, 해당 인덱스(i) 앞 부분의 수(j)를 모두 체크 만약 앞 부분의 dp[j]가 현재 인덱스의 dp[i]보다 작지 않고, A[j] 가 A[i] 보다.. 2021. 12. 16. 이전 1 다음
