Study Log

점화식 초기 상태각 원소는 그 자체로 하나의 증가 부분 수열을 형성합니다.따라서 초기값:dp[i]=A[i](최소 합은 자기 자신)상태 전이인덱스 ii에서 가능한 이전 원소 jj를 탐색합니다:dp[i]=max⁡(dp[i], dp[j]+A[i]) (for all jdp[j]+A[i]: A[j]를 포함한 증가 부분 수열에 A[i]A[i]를 추가한 경우의 합.최종 결과모든 ii에 대해 dp[i]를 계산한 후:최대 합=max⁡(dp[0],dp[1],…,dp[n−1])  코드import java.io.*;public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new Buff..

https://www.acmicpc.net/problem/2156문제 분석 과정이전에 두 잔을 연속으로 마셨다면 그 다음 잔은 마실 수 없습니다.최대 이전 3개의 값들까지만 기억하면 된다는 점을 이용해서 공간 최적화를 할 수 있습니다. 점화식dp[i−1]: 현재 잔 ii를 마시지 않고 이전 최적해를 그대로 가져오는 경우.dp[i−2]+array[i]: 이전 잔은 건너뛰고 현재 잔을 마시는 경우.dp[i−3]+array[i−1]+array[i]: 이전 잔과 현재 잔을 마시되, 두 칸 떨어진 잔은 건너뛰는 경우. dp[i]=max⁡(dp[i−1],dp[i−2]+array[i],dp[i−3]+array[i−1]+array[i])초기값 설정dp[0]=array[0]: 첫 번째 잔을 마시는 경우.dp[1]=arr..

https://www.acmicpc.net/problem/9465문제 접근 과정선택 가능한 경우의 수양옆 불가: 같은 열의 다른 행에 위치한 스티커를 선택할 수 없습니다.위아래 불가: 인접한 대각선 방향의 스티커도 선택할 수 없습니다.대각선 가능: 한 칸 떨어진 대각선 또는 두 칸 떨어진 대각선의 스티커는 선택 가능합니다.한 칸 떨어진 대각선: 현재 스티커와 같은 열의 반대편 스티커에서 이어지는 경우.두 칸 떨어진 대각선: 현재 스티커와 같은 열보다 2칸 앞에 있는 반대편 스티커에서 이어지는 경우.한 칸 대각선과 두 칸 대각선을 포함한 세 칸 이상의 대각선은 이미 점화식에서 표현 가능합니다. 점화식DP 배열 정의dp[0][j]: 첫 번째 행의 j번째 열 스티커를 선택했을 때 얻을 수 있는 최대 점수.dp..

https://www.acmicpc.net/problem/2193문제 접근 과정 이친수는 자리수를 기준으로 끝자리(0 또는 1)에 따라 앞의 숫자 조합이 결정됩니다.끝자리가 1인 경우:그 앞에는 반드시 0만 올 수 있습니다.끝자리가 0인 경우:그 앞에는 0과 1 모두 올 수 있습니다.  점화식DP 배열 정의:dp[length][0]: 길이가 length이고, 끝자리가 0인 이친수의 개수dp[length][1]: 길이가 length이고, 끝자리가 1인 이친수의 개수점화식:끝자리가 0인 경우:앞에 올 수 있는 숫자는 0과 1 모두 가능하므로: dp[length][0]=dp[length−1][0]+dp[length−1][1]끝자리가 1인 경우:앞에 올 수 있는 숫자는 0만 가능하므로: dp[length][1]..

https://www.acmicpc.net/problem/11057문제 접근 과정오르막 수의 개수를 계산할 때, 오름차순으로 계산하는 것이 아닌, 맨 끝자리 숫자를 고정했을 때의 관점에서 접근하는 것이 핵심입니다.끝자리 고정 관점오르막 수는 끝자리 숫자가 0부터 9 중 하나로 고정될 때, 앞의 숫자들이 어떤 값을 가질 수 있는지 계산하는 문제로 바꿀 수 있습니다.예를 들어, 길이가 2이고 끝자리 숫자가 1이라면 가능한 오르막 수는 다음과 같습니다:01, 11 (끝자리 1로 고정)길이가 3이고 끝자리 숫자가 1이라면 가능한 오르막 수는 다음과 같습니다:001, 011, 111 현재 자릿수에서 가능한 경우의 수현재 자릿수의 끝자리 숫자가 j로 고정된 경우, 이 숫자는 이전 자릿수에서 끝자리 숫자가 0부터 j..