글 읽기 - 11722 두가지 논리가 다른건가요?

q8514199 4년 전 0

안녕하세요. 메모이제이션을 통한 dp를 통해 해곃했습니다.

그런데 당연히 될거라고 생각한 비슷한 논리의 코드는 틀리더군요.

일단 맞은 저의 논리는 "특정 지점에서 가장 긴 감소하는 수열의 길이 = 특정 지점보다 작은 지점에서의 가장 긴 감소하는 수열의 길이 +1" 입니다.

모든 지점을 시작점이 될 수있다고 생각해 반복문을 사용했습니다.

반복문을 사용하지 않을 수 없을까 생각하다가 다음 방법을 고안했습니다.

그리고 비슷하게 생각한 논리는 "특정 지점에서 가장 긴 감소하는 수열의 길이 = max(특정 지점보다 작은 지점에서의 가장 긴 감소하는 수열의 길이 +1, 특정지점보다 작지 않은 지점에서의 가장 긴 감소하는 수열의 길이) 이었습니다.

이 방법을 사용하면 반복문을 사용하지 않고 풀 수 있을 거 같았는데 잘 안되네여... 밑에 코드 남길테니 봐주시면 감사하겠습니다!

//1.특정 지점에서 가장 긴 감소하는 수열의 길이 =
//특정 지점보다 작은 지점에서의 가장 긴 감소하는 수열의 길이 +1
#include <iostream>
#include <string>
#include <memory.h>
#include <algorithm>
using namespace std;
int n;
int arr[1100];
int catche[1200];
int dp(int start) {
	if (start >= n) {
		return 0;
	}
	int& ret = catche[start];
	if (ret != -1) return ret;

	ret = 1;
	for (int i = start + 1; i < n; i++) {
		if (arr[i] < arr[start]) ret = max(ret, 1 + dp(i)); 
        // 특정 지점 (start)보다 작은 지점에서의 길이+1 
	}
	return ret;
}
int main() {
	cin >> n;
	int m = 0;
	memset(catche, -1, sizeof(catche));
	for (int i = 0; i < n; i++) cin >> arr[i];
	for (int i = 0; i < n; i++) dp(i);
	for (int i = 0; i < n; i++) m = max(m, catche[i]);
	cout << m;
}

 //   2.특정 지점에서 가장 긴 감소하는 수열의 길이 = 
 //  max(특정 지점보다 작은 지점에서의 가장 긴 감소하는 수열의 길이 +1,
 //  특정지점보다 작지 않은 지점에서의 가장 긴 감소하는 수열의 길이)

#include <iostream>
#include <string>
#include <memory.h>
#include <algorithm>
using namespace std;
int n;
int arr[1100];
int catche[1200];
int dp(int start) {
   if (start>=n) {
      return 0;
   }
   int& ret = catche[start];
   if (ret != -1) return ret;

   ret = 1;
   for (int i = start + 1; i < n; i++) {
      if (arr[i] < arr[start]) ret = max(ret, 1+dp(i));
       // 특정 지점 (start)보다 작은 지점에서의 길이+1 
      else ret = max(ret, dp(i));
        // 특정 지점 (start)보다 작지 않은 지점에서의 길이
   }
   return ret;
}

int main() {
   cin >> n;
   memset(catche, -1, sizeof(catche));
   for (int i = 0; i < n; i++) cin >> arr[i];
   cout << dp(0);
}

djm03178 4년 전 0

다음과 같이 하면 틀리게 됩니다.

https://ideone.com/e3xRmW

dp(1)이 dp(2)의 반환값 2를 그대로 자신의 결과값으로 삼으면서, dp(0)이 여기에 1을 더하기 때문입니다.

djm03178 4년 전 0

1+dp(i)를 하는 것은 i번째 원소가 부분수열에 포함되는 것을 전제로 하고 있는데, 정작 dp(i) 자체에는 i번째 원소가 포함되지 않은 경우도 같이 고려되었기 때문에 발생한 문제입니다.

q8514199 4년 전 0

와.. 헛점을 정확히 짚으셨네요. 놀랍습니다.. 정말 감사드립니다! 새해 복 많이 받으세요

댓글을 작성하려면 로그인해야 합니다.