백준] 11053 : 가장 긴 증가하는 부분 수열

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

---

 

11053번: 가장 긴 증가하는 부분 수열

 

문제  : 

수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오.

예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다.

 

입력  : 

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

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

 

출력  : 

첫째 줄에 수열 A의 가장 긴 증가하는 부분 수열의 길이를 출력한다.

 

 

 

접근 방법

 

 

 내가 처음 생각한 풀이 방법

(1) 처음

arr 와 dp 배열을 준비한다.
arr는 cin >> 을 받고, dp는 dp 결과를 저장하는 방.

arr  □□□□□□...□  =>  10  20  10  30  20  50
dp  □□□□□□...□   =>   1   2           3             4 해서 result는 4

이렇게 해서 그냥 간단히 a[i]와 a[i - 1]를 비교하는 방식으로 결과를 냈더니 틀렸당..ㅎ

 

// 틀림

#include <iostream>
using namespace std;

int dp[1001], arr[1001];

int main() {
	cin.tie(0);
	ios_base::sync_with_stdio(false);
	
	int n;
	
	cin >> n;
	
	for(int i = 1; i <= n; i++){
		cin >> arr[i];
	}
	dp[1] = 1;
	
	for(int i = 2; i <= n; i++){
		if(arr[i - 1] <= arr[i]){
			dp[i] = dp[i - 1] + 1;
		}else
		dp[i] = dp[i - 1];
	}
	
	cout << dp[n];
	
	return 0;
}

 

 

(1) 두 번째

"수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오."

위의 가장 긴 증가하는 부분 수열이라는 부분을 이해하지 못했다.

이 부분을 이해하기 위해서는..
다양한 입출력 예제가 필요하지 않을까..? 해서

다른 블로그를 찾아봤다.

만약
10  20  25  11  30  12  50  60  13  20  14 가 주어진다면
가장 긴 증가하는 부분 수열은 10  11  12  13  14로 총 4이다.

따라서 이 때 필요한 것은 자신의 앞에 있는 숫자가 작은 것을 찾는 것이다.
자신보다 작은 숫자를 찾았을 때 dp[i]를 +1해주면 된다.

#include <iostream>
using namespace std;

int dp[1001], arr[1001];

int main() {
	cin.tie(0);
	ios_base::sync_with_stdio(false);
	
	int n;
	
	cin >> n;
	
	for(int i = 1; i <= n; i++){
		cin >> arr[i];
	}
	
	dp[1] = 1;
	
	for(int i = 2; i <= n; i++){
		for(int j = 1; j < i; j++){
			if(arr[i] > arr[j]){
				dp[i] = dp[j] + 1;
				
				if(dp[i - 1] < dp[i - 2]){
					dp[i] = dp[i - 2] + 1;
					break;
				}
				
			}else{
				dp[i] = dp[j];
				break;
			}
		}
	}
//	for(int i = 0; i <= n; i++){
//		cout << dp[i] << " ";
//	}
	
	cout << dp[n];
	
	return 0;
}

 

==> 엇비슷하게 점화식 세우는 방법은 맞았는데

예제 하나 출력이 맞으면 다른 하나는 틀리고....

할 수 있을 것 같은데, 막상 해보면 틀리니까 속상하다.

 

 

정답 코드

#include <iostream>
using namespace std;

int dp[1001], arr[1001];

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

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

		if(max < dp[i]){
			max = dp[i];
		}
	}
	
	cout << max;
	
	return 0;
}

 

 

 

 

참고한 블로그

[백준] 11053번 C/C++ 풀이 _ 가장 긴 증가하는 수열 - Easy is Perfect

[백준][11053번][DP] 가장 긴 증가 부분 수열