분류 전체보기

[백준] 가장 긴 감소하는 부분 수열 (11722번 JAVA) / 401 - 다이나믹 프로그래밍 1 (연습) [접근 방법] 을 아주 조금 비튼 문제이다. https://notorious.tistory.com/180 [백준] 가장 긴 증가하는 부분 수열 (!) (11053번 JAVA) / 400 - 다이나믹 프로그래밍 1 [백준] 400 - 다이나믹 프로그래밍 1 : 가장 긴 증가하는 부분 수열 (!) (11053번 JAVA) 최장 증가 부분 수열 이란...? (LIS : Longest Increasing Subsequence) : 어떤 임의의 수열이 주어질 때, 이 수열에서 볓개의 notorious.tistory.com 가장 긴 감소하는 부분 수열을 구하는 문제이다. DP를 갱신하는 조건 문을 바꾸기만 ..

[백준] 가장 큰 증가 부분 수열 (!) (11055번 JAVA) / 401 - 다이나믹 프로그래밍 1 (연습) [접근 방법] LIS 문제와 비슷하다곤 하지만, 나에겐 굉장히 어려운 문제였다. LIS는 DP 배열에 원소간의 대소 관계를 이용한 일종의 서열을 저장해 두었지만, 이번 문제에는 본인을 마지막으로 하는 증가 수열 중 가장 큰 수열원소의 합을 저장한다. 인덱스 4의 경우, [1, 2, 50]의 증가 부분 수열을 가지고 있다. 인덱스 5를 고려하기 위해서 DP의 인덱스 4에 이전 인덱스 중 가장 큰 수열원소의 합을 미리저장해 놓으면 편할 것이다. 완벽히 이해를 하지 못해 더이상의 설명은 어렵다. [JAVA 코드] import java.io.BufferedReader; import java.io.Bu..

[백준] 정수 삼각형 (1932번 JAVA) / 401 - 다이나믹 프로그래밍 1 (연습) [접근 방법] 이 문제는 상당히 유명한 DP 활용 문제이다. 1. 삼각형의 cost를 2차원 배열로 정의 한다. 2. cost 배열의 원소를 누적합 중 최댓값으로 갱신한다. 3. n 열의 값 (총 경로의 cost 누적합) 중 최댓값을 도출한다. int max = 0; for(int i=1; i

[백준] 포도주 시식 (2156번 JAVA) (!) / 401 - 다이나믹 프로그래밍 1 (연습) [접근 방법] import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.IOException; import java.io.InputStreamReader; import java.io.OutputStreamWriter; import java.util.*; public class Main{ public static void main(String[] args) throws IOException{ BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); Buff..

[백준] 스티커 (9465번 JAVA) (!) / 401 - 다이나믹 프로그래밍 1 (연습) [접근 방법] (0 , 0) 을 선택한다면, 선택 가능한 곳은 (1, 2) 와 (1, 3) 이다. ※ (1 , 3) 보다 뒤 쪽을 선택한다면 최대값을 만들 수 없다. import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.IOException; import java.io.InputStreamReader; import java.io.OutputStreamWriter; import java.util.*; public class Main{ public static void main(String[] args) throws IOExcepti..

[백준] 오르막 수 (11057번 JAVA) (!) / 401 - 다이나믹 프로그래밍 1 (연습) [접근 방법] * N자리의 수이고 끝자리가 K 인 오르막 수의 개수는 "N-1 자리의 수이고 끝자리가 0~K 인 오르막 수의 개수를 모두 더한 것" 과 같다. 즉, N 자리수의 오르막 수의 총 개수는 N 자리수 이고 끝자리가 각각 0 부터 9 까지의 경우의 수를 모두 더한 것을 구하면 된다. N이 5인 경우를 예로 들겠다. 5자리수이고 끝자리 수가 5인 오르막 수의 경우의 수를 구하는 과정이다. 4자리 수이고 끝자리 수가 0 부터 5인 각각의 경우를 모두 더한 것과 같다. 5자리 수의 끝자리 수가 5인 경우를 위와 같이 구했다면, 5자리 수의 오르막 수를 모두 구하기 위해선 끝자리가 0 ~ 9 인 경우를 모..