길이가 K인 증가하는 부분 수열의 개수를 구하는 다이나믹 프로그래밍

6506번: 엘 도라도 주어진 배열에서 길이가 K인 증가하는 부분 수열의 개수를 찾는 문제 [1,2,3,4,5,6,7]에서 [2,4,6]은 증가하는 부분 수열이지만 [4,1,2]는 부분 수열이 아니다. ----------------------------------------------------------------------------------------------------------------- dp[i][x] = i번째 원소까지 봤을때, 길이가 x인 증가하는 부분 수열의 개수라고 정의해서, O(N^3)에 가장 긴 증가하는 부분 수열의 길이를 구하듯이 구해봤는데 틀리더라고 어디선가 꼬인건지 근데 dp[i][x] = "마지막 원소가 i번째 원소이면서" 길이가 x인 증가하는 부분 수열의 개수 라고 정..

• format_list_bulleted 다이나믹 프로그래밍
• · 2025. 3. 11.
• textsms

크기가 1씩 증가하는 가장 긴 증가하는 부분수열의 길이를 구하는 다이나믹 프로그래밍

15966번: 군계일학 주어진 배열에서 ai = a1 + (i-1)을 만족하는 부분 수열 a의 길이의 최댓값을 구하는 문제 -------------------------------------------------------------------------------------------------------------------------------------------------- 그런데 가장 긴 증가하는 부분 수열을 찾는거니까 O(N^2)인가? 근데 N이 10만인데? 그러면 O(N)에 찾을 수 있다는건가? 한참 고민했다.. 갑자기 번뜩이는?아이디어가 떠올랐다 먼저 핵심은 ai = a1 + (i-1)을 만족하는 수열은 무엇을 의미하는가? a1 = 1이면 a2 = 2, a3 = 3,.... a1 = 2이..

• format_list_bulleted 다이나믹 프로그래밍
• · 2025. 3. 10.
• textsms

두 팀중 적어도 한 팀이 소수만큼 점수를 얻을 확률

1344번: 축구  90분간 이루어지는 축구 경기를 5분 간격으로 나눈다. 처음 간격은 처음 5분, 두번째 간격은 그 다음 5분... 각 간격에서 A,B팀이 각각 득점할 확률이 주어진다 각 간격에서 A,B팀은 각각 많아야 한골씩 득점할 수 있다 경기가 끝났을 때 적어도 한 팀이 소수로 득점할 확률은? ------------------------------------------------------------------------------------------------------------------------------------ 5분씩 간격이 나눠지고 전체 경기 시간은 90분이므로 총 18간격씩 이루어진다 각 간격에서 두 팀은 독립적으로 최대 1골씩 넣을 수 있다 dp[i][a][b] = i번째 간..

• format_list_bulleted 다이나믹 프로그래밍
• · 2025. 3. 2.
• textsms

구간의 시작과 끝중 하나를 선택할 수 있는 다이나믹 프로그래밍

1823번: 수확  왼쪽부터 오른쪽으로 n개의 벼가 있는데, 매번 맨 왼쪽 혹은 맨 오른쪽 중 하나를 수확할 수 있다 k번째 수확할때 그 벼의 가치가 A[i]라면, A[i] * k의 이익을 얻는다 n개의 벼를 모두 수확할 때 얻는 최대 이익은? --------------------------------------------------------------------------------------------------------------------------------------------------- dp[i][j]를 [i,j] 구간에서 벼를 수확할 때 얻는 최대 이익이라고 정의 i번째 벼를 수확하거나, j번째 벼를 수확할 수 있다 [i,j] 구간에 벼가 있다면 0 ~ i-1의 벼랑 j+1 ~ n-1..

• format_list_bulleted 다이나믹 프로그래밍
• · 2025. 2. 26.
• textsms

배열의 모든 수의 관계가 약수 배수 관계가 되도록 만드는 다이나믹 프로그래밍

19576번: 약수 주어진 배열의 어떤 수를 양의 정수로 바꿔서 임의의 두 수 x,y를 골랐을 때 x가 y로 나누어 떨어지거나, y가 x로 나누어 떨어지도록 만들고 싶다. 이때 양의 정수로 바꾸는 행위를 최소로 하고자 할 때 최소 몇번 바꿔야하는가? --------------------------------------------------------------------------------------------------------------------------------------------------------------- 어떤 수로 바꾸는가?에 대한 문제는 되지 않는다  1은 모든 수의 약수이기 때문에 그냥 1로 바꾸면 되기 때문이다. 그렇다면 몇번 바꿔야하는지는 어떻게 알아내는가? 주어진 배열..

• format_list_bulleted 다이나믹 프로그래밍
• · 2025. 2. 24.
• textsms

문자를 하나만 바꾸거나, 처음부터 연속된 k개를 바꿔서 전부 같은 문자로 바꾸는 다이나믹 프로그래밍

2806번: DNA 발견 A나 B로 이루어진 문자열에서 첫번째 연산은 하나의 문자를 A는 B로, B는 A로 바꾸는 것이다. 두번째 연산은 처음부터 연속된 K(1  예를 들어 ABBA라면, B 2개를 각각 A로 바꾸면 AAAA가 되고 처음부터 3개의 문자 ABB를 뒤집어서 BAA로 바꾸고, BAAA에서 첫번째 문자 B를 A로 바꾸면 2회만에 AAAA로 된다. 이러한 두 연산으로 모든 문자를 A로 바꾸고 싶다 가능한 최소 연산 횟수는? ----------------------------------------------------------------------------------------------------------------------------------------------------------..

• format_list_bulleted 다이나믹 프로그래밍
• · 2025. 2. 23.
• textsms