굳건하게

문제 :  https://www.acmicpc.net/problem/2003

[알고리즘풀이]

배열의 원소의 값이 변하지 않으므로, 다이나믹 프로그래밍을 이용해 문제를 풀 수 있다.

( 자세한 설명 : https://travelbeeee.tistory.com/115 )

#include<iostream>

using namespace std;

int N[10000];

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	int n, m;
	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		cin >> N[i];
		if (i != 0)
			N[i] += N[i - 1];
	}
	int ans = 0;
	for(int i = 0; i < n; i++)
		for (int j = i; j < n; j++) {
			if (i == 0) {
				if (N[j] == m)
					ans++;
			}
			else{
				if (N[j] - N[i - 1] == m)
					ans++;
			}
		}
	cout << ans;
}

안녕하세요, 여행벌입니다.

오늘은 간단하게 배열의 구간의 합을 쉽게 구하는 방법에 대해서 포스팅하겠습니다.

배열의 값들이 바뀐다면, 세그먼트 트리를 이용해야 하지만

배열의 값이 바뀌지 않는다면, DP를 이용해 쉽게 구간의 합을 구할 수 있습니다.

[배열의 합 구하기]

A[ N ] : 원소들이 N개 들어있는 배열

이때, A[ i ] ~ A[ j ]까지의 합을 여러 번 구해야 된다고 가정합시다.

먼저, 새로운 배열을 하나 정의하겠습니다.

S [ N ] : A배열의 첫번 째 원소부터 K번째 원소까지의 합을 저장한 배열. ( S[ k ] = A [0] + A [1] + ⋯ + A [k] )

그러면, A [ i ] ~ A[ j ] 까지의 합 = S[ j ] - S[ i - 1]이 성립합니다.

또, S[ K ] = S[ K - 1 ] + A[ K ]와 같은 점화식이 성립합니다.

이 두 가지 사실을 이용해 S 배열을 빠르게 채우고, S 배열의 값을 이용해 구간의 합을 구한다면,

굉장히 빠르게 구할 수 있습니다.

실습을 해보겠습니다.

#include<iostream>

using namespace std;

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	
	int A[10], S[10];
	cout << "A배열의 원소를 10개 입력하시오.\n";
	for (int i = 0; i < 10; i++)
		cin >> A[i];
	S[0] = A[0];
	for (int i = 1; i < 10; i++)
		S[i] = S[i - 1] + A[i];
	cout << "완성된 S배열입니다.\n";
	for (int i = 0; i < 10; i++)
		cout << S[i] << ' ';
	cout << '\n';
}

Input
1 2 3 4 5 6 7 8 9 10

위의 코드에 Input으로 다음과 같이 입력하면, S배열은 어떻게 출력될까요?

완성된 S배열입니다.
1 3 6 10 15 21 28 36 45 55

다음과 같겠죠?

O(n) 만에 우리가 원하는 S 배열을 만들 수 있습니다!

만약, A 배열의 구간의 합을 M번 구해야 되는 문제가 있다면, 2중 포문을 이용해 구해준다면 O(N * M)이 될 것입니다.

하지만 S 배열을 만들어주고, S배열 값을 이용해 M번 A배열의 구간의 합을 구해준다면 O(N + M)으로

훨씬 효율적인 프로그램을 만들 수 있습니다.

추천 문제
https://www.acmicpc.net/problem/2003
https://www.acmicpc.net/problem/11441
https://www.acmicpc.net/problem/11659

문제 : https://www.acmicpc.net/problem/10819

[알고리즘풀이]

Input 범위가 작으므로, Backtracking을 이용해서 가능한 모든 배열 순서를 탐색한다.

#include<iostream>
#include<vector>
#include<cmath>

using namespace std;

vector<int> v;
bool check[8];
int n, ans = -1, A[8];

void bt(void) {
	if (v.size() == n) {
		int temp = 0;
		for (int i = 0; i < n - 1; i++) {
			temp += (int)(abs(A[v[i]] - A[v[i + 1]]));
		}
		if (temp > ans)
			ans = temp;
		return;
	}
	for (int i = 0; i < n; i++) {
		if (check[i] == false) {
			v.push_back(i);
			check[i] = true;
			bt();
			check[i] = false;
			v.pop_back();
		}
	}
	return;
}
int main(void) {
	ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);

	cin >> n;
	for (int i = 0; i < n; i++)
		cin >> A[i];

	for (int i = 0; i < n; i++) {
		v.push_back(i);
		check[i] = true;
		bt();
		check[i] = false;
		v.pop_back();
	}
	cout << ans;

}

문제 : https://www.acmicpc.net/problem/1520

[알고리즘풀이]

경로를 DFS로 역으로 탐색하며, 경우의 수를 저장한다.

dp[i][j] : (i , j )부터 목표 지점인 (0, 0)까지 가는 경우의 수.

이때, dp[i][j]에 밟아보지 않은 지점과 밟았는데 (0, 0)까지 가는 경로가 없는 경우를 구분해줘야 된다.

그렇지 않으면, 밟았던 경로도 다시 탐색하기 때문에 시간 초과에 걸린다.

따라서, 밟아보지 않은 지점에는 dp[i][j] = -1 을 저장하고, 경로가 없는 경우에는 dp[i][j] = 0이 저장되게,

dp[][] 배열을 -1로 초기화해줘야 한다.

#include<iostream>
#include<vector>
#include<queue>

using namespace std;

int N, M, map[500][500], dp[500][500];
int dir_x[4] = { -1,0,1,0 }, dir_y[4] = { 0, 1, 0, -1 };

int get_count(int, int);

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	cin >> N >> M;
	for (int i = 0; i < N; i++){
		for (int j = 0; j < M; j++){
			cin >> map[i][j];
			dp[i][j] = -1;
		}
	}
	cout << get_count(N - 1, M - 1);
}

int get_count(int i, int j) {
	if (dp[i][j] != -1)
		return dp[i][j];
	if (i == 0 && j == 0)
		return 1;
	dp[i][j] = 0;
	for (int k = 0; k < 4; k++) {
		int s_x = i + dir_x[k];
		int s_y = j + dir_y[k];
		if (0 <= s_x && s_x < N && 0 <= s_y && s_y < M && map[i][j] < map[s_x][s_y]) {
			dp[i][j] += get_count(s_x, s_y);
		}
	}
	return dp[i][j];
}