백준] 11055 : 가장 큰 증가 부분 수열

BOJ에서 다음 문제들을 쭉 순서대로 풀어본다.  boj.kr/문제번호 <= 형태로 검색하면 된다.

DP - 1463, 11726, 11727, 9095, 10844, 11057, 2193, 9465, 2156, 11053, 11055, 11722, 11054, 1912, 2579, 1699, 2133, 9461, 2225, 2011, 11052

 

 

1시간 넘어가면 풀던 짓을 그만두고 반드시 AC받은 코드 찾아보기 (설명이 꼭 달려있는 코드를 읽자)

그리고 푼 다음에는 반드시 다른 사람의 코드를 봐야 한다.

특히 자신만의 가상의 스승을 잡고 그 분의 코드를 보는 것도 좋은 방법이라 생각한다.

너무 갓갓들은 이상한 방식으로도 짜는 경우도 있기 때문에 적당한 사람을 선택해야 한다.

 

알고리즘 문제풀이(PS) 시작하기

 

내가 애용하는 IDE 사이트

(IDE 자동 완성이 불가능하기 때문에 사용하는 중)

Ideone.com

---

 

11055번: 가장 큰 증가 부분 수열

 

문제  : 

수열 A가 주어졌을 때, 그 수열의 증가 부분 수열 중에서 합이 가장 큰 것을 구하는 프로그램을 작성하시오.

예를 들어, 수열 A = {1, 100, 2, 50, 60, 3, 5, 6, 7, 8} 인 경우에 합이 가장 큰 증가 부분 수열은 A = {1, 100, 2, 50, 60, 3, 5, 6, 7, 8} 이고, 합은 113이다.

 

입력  : 

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

둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000)

 

출력  : 

첫째 줄에 수열 A의 합이 가장 큰 증가 부분 수열의 합을 출력한다.

 

 

 

 

접근 방법

 

 

 

 

 

...

처음에 시도했던 방법들

#include <iostream>
using namespace std;

int arr[1001], dp[1001];

int main() {
    //cin.tie(0);
	//ios_base::sync_with_stdio(false);

	int n, max = 0;
	
	cin >> n;
	
	for(int i = 0; i < n; i++){
		cin >> arr[i];
	}
	
	for(int i = 0; i < n; i++){
		dp[i] = arr[i];
		
		for(int j = 0; j < i; j++) {
			
			if(arr[i] > arr[j]){
				dp[i] = dp[j] + arr[i];
			}
			else if(arr[i] == dp[j]){
				dp[i] = arr[i];
			}
		}
		if(max < dp[i]){
			max = dp[i];
		}
	}

	cout << max;
	
	return 0;
}

 

첫 번째 시도.

처음에는 else if 부분을 추가하지 않았다.

하지만 다른 예제를 적용했을 때,

1  1  50  101  100  2...를 입력받으면

출력되는 dp[i]는 1 0 50 101... 이었다.

(원래대로라면 1 0 51 152... 가 되어야 한다.)

 

이를 해결하기 위해 dp[j]와 arr[i]가 같다면 dp[i]에 arr[i] 값을 넣어줬다.

 

그렇게 해서 IDE에서는 맞았지만, 백준에서는 틀렸다고 나왔다.

 

 

두 번째 시도.

왜 틀렸는지... 이유를 찾기 위해서 다른 예제도 적용해봤다.

1  1  2  3  1  5를 arr에 입력했다.

그러자 dp[i]의 출력물은 1  1  3  6  1  6 이었다.

6이 아니라 11이 되어야 할 자리였는데, 코드가 잘못되었음을 알게되었다.

 

이를 해결하기 위해 백준 11053번 문제를 참고했다.

위의 문제와 마찬가지로 이번 문제도 dp[i]의 값끼리 비교를 해줘야 했다.

 

1  1  2  3  1  5의 dp값들이 1  1  3  6  1  6 이 되지 않기 위해...

arr값끼리도 비교하고, dp[i]의 값끼리도 비교해야 한다.

>> 큰 값을 찾기 위해

dp[i]의 값과 dp[j] + arr[i]의 값을 비교해야했다.

 

#include <iostream>
using namespace std;

int arr[1001], dp[1001];

int main() {
    //cin.tie(0);
	//ios_base::sync_with_stdio(false);

	int n, max = 0;
	
	cin >> n;
	
	for(int i = 0; i < n; i++){
		cin >> arr[i];
	}
	
	for(int i = 0; i < n; i++){
		dp[i] = arr[i];
		
		for(int j = 0; j < i; j++) {
			
			if(arr[i] > arr[j] && dp[i] < dp[j] + arr[i]){
				dp[i] = dp[j] + arr[i];
			}
		}
		if(max < dp[i]){
			max = dp[i];
		}
	}

	cout << max;
	
	return 0;
}

정답코드...

다른 코드가 있을까해서 찾아보니 내가 짠 코드와 대부분 똑같았다.

 

다른 방법도 충분히 찾을 수 있겠지만, 위의 방법이 가장 효율적일 것 같다.

 

 

 

 

정답 코드

#include <iostream>
using namespace std;

int arr[1001], dp[1001];

int main() {
	int n, max = 0;
	
	cin >> n;
	
	for(int i = 0; i < n; i++){
		cin >> arr[i];
	}
	
	for(int i = 0; i < n; i++){
		dp[i] = arr[i];
		
		for(int j = 0; j < i; j++) {
			
			if(arr[i] > arr[j] && dp[i] < dp[j] + arr[i]){
				dp[i] = dp[j] + arr[i];
			}
		}
		if(max < dp[i]){
			max = dp[i];
		}
	}

	cout << max;
	
	return 0;
}

 

 

 

 

참고한 블로그

 

-