백준 11055 가장 큰 증가 부분 수열 (JAVA 자바 풀이)
백준 11055 가장 큰 증가 부분 수열 (JAVA 자바 풀이) 📌 문제 수열 A가 주어졌을 때, 그 수열의 증가 부분 수열 중에서 합이 가장 큰 것을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {1, 100, 2, 50, 60, 3, 5, 6, 7, 8} 인 경우에 합이 가장 큰 증가 부분 수열은 A = {1, 100, 2, 50, 60, 3, 5, 6, 7, 8} 이고, 합은 113이다. ⚔ 입력 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000) 📣 출력 첫째 줄에 수열 A의 합이 가장 큰 증가 부분 수열의 합을 출력한다. 💎 문제 분석 LIS가 되는 조건이 추가된 부분이다. lis ..
2022. 12. 13.
백준 11053 가장 긴 증가하는 부분 수열 (JAVA 자바 풀이)
백준 11053 가장 긴 증가하는 부분 수열 (JAVA 자바 풀이) 📌 문제 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다. ⚔ 입력 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000) 📣 출력 첫째 줄에 수열 A의 가장 긴 증가하는 부분 수열의 길이를 출력한다. 💎 문제 분석 LIS의 기본 문제라고 한다. DP 배열을 1로 초기화 해놓고 크다면 배열을 증가시켜주어 COUNT를 올려..
2022. 12. 13.
백준 2156 포도주 시식 (JAVA 자바 풀이)
백준 2156 포도주 시식 (JAVA 자바 풀이) 📌 문제 예를 들어 6개의 포도주 잔이 있고, 각각의 잔에 순서대로 6, 10, 13, 9, 8, 1 만큼의 포도주가 들어 있을 때, 첫 번째, 두 번째, 네 번째, 다섯 번째 포도주 잔을 선택하면 총 포도주 양이 33으로 최대로 마실 수 있다. ⚔ 입력 첫째 줄에 포도주 잔의 개수 n이 주어진다. (1 ≤ n ≤ 10,000) 둘째 줄부터 n+1번째 줄까지 포도주 잔에 들어있는 포도주의 양이 순서대로 주어진다. 포도주의 양은 1,000 이하의 음이 아닌 정수이다. 📣 출력 첫째 줄에 최대로 마실 수 있는 포도주의 양을 출력한다. 💎 문제 분석 처음 풀이에서는 그림과 같이 dp[2]일때만 고려하여 직전과 직전의 직전 dp만을 계산했다. 하지만 선택을 안하..
2022. 12. 13.
