노래부르다

전형적인 DP문제이다.DP를 워낙 못하다보니, 계속해서 DP에 익숙해지고 감잡는데 초점을 맞춘다... 알고리즘 풀이입력 배열 : 입력받은 입력 배열값. 설명에서 vec이라 하겠음.dp배열 : 해당 인덱스가 최대값일 때, 수열의 최대 원소 갯수값 해당 문제는 점화식이 따로 있다기 보다는 증가하는 수열의 기본적인 문제였다. (1) 현재 vec의 인덱스 i의 원소가 하위(vec[1] ~ vec[i-1]) 원소보다 커야하는 것과 (2) (1)의 조건에 해당하는 원소 중, 길이가 가장 긴 값을 가져와서 dp배열에 +1한 수를 넣는다. 설명이 어렵다면 코드를 보면서 이해를 추가하기를 바랍니다. #include #include using namespace std;int main() { ios::sync_with..

https://www.acmicpc.net/problem/2096문제 분석문제 조건생각보다 단순한 문제다. 행은 N(입력값), 열은 3인 배열에서 이동할 수 있는 제약이 있고 이들의 최대/최소값을 구하는 문제이다. 문제를 보자마자 무조건 dp겠다 싶었다. 그래서... dp임은 인지했지만, 답이 잘 나왔음에도 메모리가 초과되었다는 것을 보았다. 4MB????🤔: 대체 4MB는 뭐야?! 문제에서는 N의 최대값은 10만인데... 입력값만 받아도 최대 30만 데이터를 저장하는 배열을 만들어야하는데?이걸 어떻게 풀라는거야...문제 풀이DP문제를 풀기 위해서는 무조건 이전에 계산했던 최적의 값들을 무조건 저장해둬야한다고 생각했다... 그래서 처음 생각했던 오답풀이는 이러하다... ⚠️오답풀이!!!⚠️☠️ 1. 입..

1149번: RGB거리 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net 문제 분석 문제는 (1) 모든 집을 칠하는 최솟값을 구하고자 한다. N개의 집이 순서대로 있고, i번째 집을 기준으로 i - 1번째, i + 1번째 집은 i번째와 색이 같지 않아야 한다. (2) 즉, 내 집과 양 옆집의 색이 겹치지만 않으면 된다. 집마다 칠할 수 있는 빨, 초, 파 색의 가격이 각각 주어지고, 이의 최솟값을 구해야한다. 🤫 : 음... 각 집마다 칠할 수 있는 가장 싼 색을 고르면, 옆 집이랑 겹칠수도 있고... 그렇다고 ..