백준 11055번(가장 큰 증가부분수열)

jh Seo·2022년 8월 19일

다이나믹 프로그래밍 백준 한번에 못 푼 문제

백준

목록 보기

41/194

개요

[링크]백준 11055번:

입력
첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000)이 주어진다.

둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000)
출력
첫째 줄에 수열 A의 합이 가장 큰 증가 부분 수열의 합을 출력한다.

접근 방식

무난하게 dp를 떠올리고 모든 값에 대해 조사하려 했다.
함수를 pos위치부터 끝까지 조사해서 제일 긴 증가수열의 합을 return하는 함수를 구현했다.

//pos위치부터 끝까지의 값중 최대 길이 수열의 합 return
int solution(int pos) {
	//끝에 다다르면 1 return
	if (pos == amount) return 1;
	//dp배열값 참조
	int& ret = dp[pos];
	//이미 구해놓은 값이면 그 값 반환
	if (ret != -1) return ret;
	
	//0으로 초기화
	ret = 0;
	//pos부터 끝까지의 원소를 다 비교해 더 큰값이 있다면 
	//해당 값에서 다시 solution함수 호출해서 제일 큰값을 ret에 넣음
	for (int i = pos; i < amount; i++) {
		if (inputArr[pos] < inputArr[i]) ret = max(ret, solution(i));
	}
    return ret;

그 동안 푼 다이나믹 프로그래밍의 방식으로 구현을 했으나
최댓값들을 다 더한 값을 어떤 식으로 반환 할지 몰랐다.

만약 가장 긴 수열의 길이를 구하는 문제면 1을 더해서 return했겠지만
큰 값들을 다 더하는 부분은 아리송했다.

고민하다가 위의 코드에 sum변수를 선언한 후,
sum에 단순히 ret값을 더했더니 답이 안나와서 고민하다가 찾아봤다.

잘못된 점은 입력값을 비교만하고 더하는 걸 구현 안해서 답이 안나오는 것이였다.
마지막에 return ret;이 아니라

return ret+inputArr[pos];

구문을 이용해 각 값을 더해서 반환해야 정상적으로 작동한다.

하지만 이 방법도 예제만 풀릴 뿐 "틀렸습니다" 가 떠서 더 고민을 했는데,
이유는 저 코드는 pos일때의 값을 기준으로 다 비교하기 때문에
pos일때 값이 무조건 포함되어서

solution(0)을 호출해 답을 출력하면 inputArr[0]값보다 큰 값들을 조사하기 때문에,
만약 0일때 제일 작은 값이 아니라면 답이 안나온다.

따라서 solution(0)~solution(n)까지 모든 값들을 비교한 후 답을 출력해야한다.

코드

#include<iostream>
#include<memory.h>

using namespace std;
int amount = 0, dp[1001], inputArr[1001];

void input() {
	cin >> amount;
	for (int i = 0; i < amount; i++) {
		cin >> inputArr[i];
	}
	memset(dp, -1, sizeof(dp));
}

//pos위치부터 끝까지의 값중 최대 길이 수열의 합 return
int solution(int pos) {
	//끝에 다다르면 1 return
	if (pos == amount) return 1;
	//dp배열값 참조
	int& ret = dp[pos];
	//이미 구해놓은 값이면 그 값 반환
	if (ret != -1) return ret;
	
	//0으로 초기화
	ret = 0;
	//pos부터 끝까지의 원소를 다 비교해 더 큰값이 있다면 
	//해당 값에서 다시 solution함수 호출해서 제일 큰값을 ret에 넣음
	for (int i = pos; i < amount; i++) {
		if (inputArr[pos] < inputArr[i]) ret = max(ret, solution(i));
	}

	//여기서 sum을 어떻게 반환할까 고민하다가 그냥 ret자체를 return햇는데 그냥 각 값을 더하면 되는거군
	return ret+=inputArr[pos];
}

int main() {
	input();
	//solution함수에서 비교하는 값을 들여다보면 해당 pos값부터 무조건 시작하게 짜여있어서 모든 pos값에 대해 해봐야함
	int ans=0;
	for(int i=0;i<amount;i++)
	ans = max(ans,solution(i));
	cout << ans;
}