백준] 11722 : 가장 긴 감소하는 부분 수열

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

---

 

11722번: 가장 긴 감소하는 부분 수열

문제  : 

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

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

 

입력  : 

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

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

 

출력  : 

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

 

 

 

 

 

접근 방법은

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

와 유사합니다.

다만, 11053은 자신보다 작은 값을 찾았다면

이 문제는 자신보다 큰 값을 찾으면 됩니다.

 

 

 

 

 

 

 

 

 

 

...

처음에 시도했던 방법들

#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];
	}
	
	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;
    cout << dp[n - 1];
	
	return 0;
}

처음에 dp짤 때 오 완벽하다. 했는데

막상 제출해보니 틀렸다가 떴다..ㅎ

 

검색해보고 & 이전 코드와 비교해보니

위 코드에 주석 처리한 부분으로 안 적었기 때뮨...

 

바로 dp[n - 1]을 출력해서 틀렸다고 떴당.

 

역시.. IDE에서 출력이 맞았다고 해서 다 맞은 게 아니다.

그리고 위의 문제는 가장 큰 값을 찾는 것이기 때문에 dp값 중에서 max값을 비교해주는 게 맞다.

 

 

 

 

 

정답 코드

#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];
	}
	
	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;
}

 

 

 

 

참고한 블로그

 

-