Study Log

[Java] 11054. 가장 긴 바이토닉 부분 수열

https://www.acmicpc.net/problem/11054 문제 접근 과정 바이토닉 수열의 정의먼저 증가하다가 그 이후 감소하는 수열.예시: [1, 3, 5, 4, 2]각 위치를 기준으로 생각할 때,왼쪽에서 오른쪽으로 봤을 때 증가 수열의 길이를 구함.오른쪽에서 왼쪽으로 감소하는 수열의 길이를 따로 구함.그 후 두 결과를 합치면 바이토닉 수열이 됩니다.DP 정의 방법increase[i] : i번째 수가 마지막인 증가하는 수열 중 가장 긴 길이decrease[i] : i번째 수가 처음인 감소하는 수열 중 가장 긴 길이increase: 왼쪽→오른쪽 방향으로 증가 수열 길이decrease : 오른쪽→왼쪽 방향으로 감소 수열 길이점화식increase[i] = Math.max(increase[i], in..

[Java] 11722. 가장 긴 감소하는 부분 수열

https://www.acmicpc.net/problem/11722 문제 접근 과정 주어진 배열에서 각 원소를 마지막 원소로 하는 최장 증가 부분 수열의 길이를 저장하는 dp 배열을 사용점화식:dp[i] = max(dp[j] + 1) (단, j  array[j] 최종적으로 dp 배열에서 최댓값을 찾으면 가장 긴 증가하는 부분 수열의 길이를 구할 수 있습니다. 코드import java.io.*;import java.util.*;public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in));..

점화식 초기 상태각 원소는 그 자체로 하나의 증가 부분 수열을 형성합니다.따라서 초기값: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..

https://www.acmicpc.net/problem/10844문제 접근 과정1자리 수는 모두 계단 수로 정의됩니다.1자리 수는 1부터 9까지 존재하며, 이는 모두 계단 수의 조건을 만족합니다. 따라서, 길이가 1인 경우 각각의 숫자(1~9)는 계단 수의 개수가 1개씩입니다.예외적으로, 문제에서 0으로 시작하는 수는 계단 수로 간주하지 않습니다.자릿수가 증가할 때, 숫자가 뒤에 추가된다고 가정합니다.숫자가 앞에 추가된다고 보는 것보다 뒤에 추가된다고 생각하는 편이 직관적입니다. 예를 들어, 길이가 3인 경우는 길이가 2인 계단 수의 뒤에 숫자를 추가하여 구성할 수 있습니다.예를 들어, 길이가 2인 계단 수 12에 숫자 3을 추가하면, 길이가 3인 계단 수 123이 됩니다.특수한 경우: 마지막 자리가 ..

https://www.acmicpc.net/problem/6603 문제 분석확률과 통계에서 배웠던 조합 nCr을 구현하는 문제입니다.  로또 번호니까 여기서는 nC6으로 고정되어있는 상황입니다. 재귀를 통해 Brute force를 하면 단순하게 구할 수 있을 것 같다고 생각을 했습니다. 정답 코드#include #include using namespace std;void pick_number(vector &v, vector &picked, int start, int rest_pick){ if(rest_pick == 0){ for(int i = 0; i > n; if(n == 0) break; vector v(n); for(int i = 0; i > ..