노래부르다

전형적인 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..

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