이것 저것 &

문제링크: https://www.acmicpc.net/problem/2225

생각하는 과정이 필요한 문제였습니다. 각각의 결과값들을 순차대로 구하다 보면 규칙을 찾을 수 있습니다.

점화식만 구하면 쉽게 구현할 수 있는 문제였습니다.

n = 5 k = 4 의 예제를 살펴보겠습니다.

dp[k]은 dp[k][0] ~ dp[k][n]의 합이 됩니다. 그리고 각각의 dp[k][i] 는 dp[k-1][i] ~ dp[k-1][n] 까지의 합이 됩니다. 

비교적 쉽게 점화식을 구할 수 있습니다. 

그래서 ex) 5 4의 결과값은 21+15+10+6+3+1 = ? 이 되겠죠 ㅎㅎ

그다음으로 주의하셔야 할 것은 %연산을 해주는 위치와 숫자 범위입니다. 매번 dp[k-1][i] ~ dp[k-1][n] 의 연산마다 %1000000000연산을 해줘도 해당문제에서는 상관없습니다. 하지만 조금더 컴팩트 하게 코딩하기 위해서 dp[k][i] 에서만 %1000000000연산을 해주고 싶었습니다. 

근데 만약 dp[k-1] 의 합이 다 10^9를 초과해서 오버플로우가 난다면, 에러가 날 수 밖에 없습니다. 그래서 long long 을 사용해서 배열을 구현했습니다.

아래는 정답코드입니다. :) 직접 표를 작성해보시고 점화식을 시그마형태로 구하고 구현해보세요! 화이팅

#include <iostream>
using namespace std;
long long dp[202][202] = { 0 };
int n, k;
long long result = 0;

int main() {
	cin >> n >> k;
	dp[1][n] = 1; // 초기값 설정
	for (int i = 1; i <= k; i++) {		
		for (int j = 0; j <= n; j++) {
			for (int u = j; u <= n; u++)
				dp[i][j] += dp[i - 1][u];
			dp[i][j] %= 1000000000;
		}
	}
	
	for (int i = 0; i <= n; i++)
		result += dp[k][i];
	result %= 1000000000;
	cout << result << endl;
}

문제링크:https://www.acmicpc.net/problem/11722

전형적인 LIS 문제였습니다. 

LIS 개념을 아신다면 어렵지 않은 문제였습니다.

그나마 주의해야 할 점은 이전 dp값을 전부 확인해봐야한다는 것입니다. 

바로 이전의 자신보다 큰값만 비교할 경우 예외가 발생합니다. 

Ex) 5

     10 5 4 6 3

정답코드입니다. 화이팅 :)

#include <iostream>
using namespace std;
int dp[1001] = { 0 };
int arr[1001] = { 0 };
int n,num,result =0;
int main() {
	cin >> n;

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

문제링크: https://www.acmicpc.net/problem/2352

꽤나 애를 먹었습니다.

문제를 읽고 dp문제인 것을 인지했습니다. 

이 문제는 dp알고리즘 중에서도 LIS( Longest Increasing Subsequence) 입니다.

최대 부분 증가 수열이라고도 합니다.

만약 

10 20 40 30 70 50 60  의 배열이 있을때

10 20 30 50 60 이 최대 부분 증가 수열로써 가장 길이가 깁니다.

아래와 같은 뉘앙스로 해결해주면 됩니다.

#include <iostream>
using namespace std;

struct info {
	int count;
	int port_num;
};
int n,result=0;
struct info dp[40001];

int main() {
	cin >> n;
	for (int i = 1; i <= n; i++)
		cin >> dp[i].port_num;

	dp[1].count = 1; //초기값 설정

	for (int i = 2; i <= n; i++) {

		for (int j = i - 1; j > 0; j--) {
			if (dp[i].port_num > dp[j].port_num &&dp[i].count < dp[j].count)
				dp[i].count = dp[j].count;
		}
		dp[i].count++;
		if (result < dp[i].count)
			result = dp[i].count;
	}
	cout << result << endl;
}

 
하지만 문제가 생깁니다. 위의 알고리즘은 O(n^2)을 가지게 됩니다.

이 문제에서는  n(1 ≤ n ≤ 40,000) 입니다. 즉, 최악의 경우에 O(n^2) = 40000 X 40000 = 1,600,000,000 이 되기 때문에 시간제한 2초로는 어림도 없죠 ( 1억번 연산 당 대략 1초)

즉 O(n) or O(nlgn)의 풀이법을 찾아야합니다. 해당 문제에서 이전값들을 비교해서 결과를 도출해야 하기 때문에 O(n)은 불가능합니다.

C++ stl에서 제공하는 기능은 1.Lower Bound 2.인덱스 트리 입니다. (정확한 메소드내용은 모르겠지만 탐색시 O(lgn)번의 탐색으로 위치를 전달합니다. 

함수들에 관한 자세한 설명은  출처:https://dyngina.tistory.com/16

제가 만든 정답 코드입니다.

#include <iostream>
#include <algorithm>
using namespace std;

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

	arr2[len] = arr[1]; //초기값 설정
	
	for (int i = 2; i <= n; i++) {
		if (arr2[len] < arr[i]) {
			arr2[++len] = arr[i];
		}
		else {
			int val = lower_bound(arr2 + 1, arr2 + len + 1, arr[i]) - arr2;
			arr2[val] = arr[i];
		
		}
		
	}
	
	cout << len << endl;
}

생각해보니 arr는 필요가 없더군요 매번 값을 입력받고 arr2에 저장해주면 됩니다.

그리고 lower_bound메소드의 역할을 이분탐색을 통해서 구현을 할 수 도 있겠군요.

#include <stdio.h>
#define M 40010
int port[M];
int up[M] = { 0x80000001, };
int ref[M];
int n, max;

int search(int left, int right, int x) {
	int mid;

	if (left > right) return left;

	mid = (left + right) / 2;

	if (ref[mid] < x)
		return search(mid + 1, right, x);
	else if (ref[mid] > x)
		return search(left, mid - 1, x);
	else
		return mid;
}

int main() {
	int i, cursor;
	scanf("%d", &n);
	for (i = 1; i <= n; i++) {
		scanf("%d", port + i);
		cursor = search(0, max, port[i]);
		ref[cursor] = port[i];
		up[i] = cursor;
		if (cursor > max)
			max = cursor;
	}
	printf("%d\n", max);
	return 0;
}

전형적인 dp문제입니다.

반복문으로 arr배열을 탐색하면서 

자신보다 arr값이 작고 dp값이 가장큰 값에 자신의 arr값을 더한값이 dp값이 되는 점화식입니다. 

즉 , dp[i] = arr[i] + dp[maxed_index]의 형태가 됩니다.

전체코드입니다:)

#include <iostream>
using namespace std;

int n, result = 0;
int arr[1001] = { 0 };
int dp[1001] = { 0 };


int main() {
	cin >> n;

	for (int i = 1; i <= n; i++) 
		cin >> arr[i];
	
	for (int i = 1; i <= n; i++) {
		int maxed = 0,maxed_index=0;
		for (int j = i - 1; j >= 1; j--) {
			if (arr[j] < arr[i] && maxed < dp[j] )
				maxed = dp[j], maxed_index = j;
		}
		dp[i] = arr[i] + dp[maxed_index];
		if (result < dp[i]) result = dp[i];
	}

	cout << result << endl;
}

쉬운 dp 문제입니다.

P(1)부터 P(11)까지 첫 11개 숫자는 1, 1, 1, 2, 2, 3, 4, 5, 7, 9, 12, 16 ... 

 dp[n] = dp[n-1] + dp[n-5] 라는 점화식을 찾을 수 있게 됩니다.

정답률이 30%대라는게 믿기지 않을 정도로 쉬워서 의아하며, 

ㅋㅋㅋㅋㅋㅋㅋㅋ

한번 틀렸습니다. 숫자가 증가함에 따라 기하급수적으로 수가 커지는거를 신경못썻습니다. 

int형은 4byte = 32bit = 2의 32승

즉 2,147,483,648x2 만큼의 수를 저장할 수 있습니다.

음수,0양수 모두를 포함해야하기 때문에 아래 표와 같은 범위의 수를 표현할 수 있게 됩니다.

수가 넘어갈때는 제일 아래의 음수값 - 2,147,483,648로 내려가 1씩 올라가며 출력을 하는 구조입니다.

저는 c++에서 long long 형을 사용하여 문제를 해결하였습니다. 

정답코드

#include <iostream>
using namespace std;

long long dp[101] = { 0 };
int t = 0, n;
int main() {
	dp[1] = 1, dp[2] = 1, dp[3] = 1, dp[4] = 2;
	for (int i = 5; i <= 100; i++)
		dp[i] = dp[i - 1] + dp[i - 5];

	cin >> t;

	while (t--) {
		cin >> n;
		cout << dp[n] << endl;
	}
}

실패코드를 먼저 보여드립니다.

#include <iostream>
#include <cmath>
using namespace std;
int dp[100001] = { 0 };

int main() {
	int n = 0;
	cin >> n;
	dp[0] = 0, dp[1] = 1, dp[2] = 2;

	for (int i = 3; i <= n; i++) {
		int num = pow(i,0.5);
		dp[i] = 1 + dp[i - num*num];
		cout << dp[i] << endl;
	}
	cout << dp[n] << endl;
}

반례가 있습니다.

12 = 3*2 + 1 + 1 + 1 = 4

12 = 2*2 + 2*2 + 2*2 = 3

명백하게 그리디적인 관점에서 문제를 해결나갈 수 없는 것을 보실 수 있습니다.

즉, 제곱값이 자신보다 작은 모든 제곱근들에서의 경우의 수를 비교해주어 결과값을 도출하여야 하는 문제입니다. 

#include <iostream>
#include <cmath>
using namespace std;
int dp[100001] = { 0 };

int main() {
	int n = 0;
	cin >> n;
	dp[0] = 0, dp[1] = 1, dp[2] = 2;

	for (int i = 3; i <= n; i++) {
		int num = pow(i,0.5);
		dp[i] = 1 + dp[i - num*num];
		for (int j = num-1; j >= 1; j--) {
			if( (1 + dp[i - j*j]) < dp[i] )
				dp[i] = 1 + dp[i - j*j];
		}
	}
	cout << dp[n] << endl;
}

전형적인 dp문제입니다.

점화식을 고려할때 머리로 연상되지 않습니다.

표를 그리며 차근차근 풀어나가보았습니다.  

예시입력에 경우
        k   0   1   2   3   4   5   6   7   8   9   10
c(0)    [0] 1   0   0   0   0   0   0   0   0   0   0
c(1)    [1] 1   1   1   1   1   1   1   1   1   1   1
c(2)    [2] 1   1   2   2   3   3   4   4   5   5   6
c(3)    [5] 1   1   2   2   3   4   5   6   7   8   10

1의 경우에는 모두 1가지 경우의수를 가지게 되고

2를 포함할 경우 2의 배수마다 경우가 한가지씩 증가하는 것을 확인 할 수 있었습니다.

즉, 2를 포함할 때 1의 경우+ DP[N-2] + 1 의 경우가 됨을 확인할 수 있습니다. 

5를 포함할 때에는 (1의경우가 포함된) 2의 경우 + DP[N-5] + 1 이 됨을 확인할 수 있었습니다. 

즉 점화식을 나타내면 

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

	}

네 메모리 초과입니다.. :) ㅋㅋㅋ

문제조건이 4MB였네요. 

int형은 4byte이고 n=100까지, k=10000까지이니 dp 2차원 배열은 4000,000byte= 4000kbyte = 4mbyte이므로 메모리 초과가 나는것입니다. 직관적으로 점화식이 변화하는것을 확인했기때문에 dp[101][10001] 를 dp[10001]로 줄여보겠습니다. 

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

전체코드입니다. 

#include <iostream>

using namespace std;

int dp[10001] = { 0 };
int n = 0, k = 0;
int arr[100] = { 0 };
int result = 0;

int main() {

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

	}
	cout << dp[k] << endl;
}