티끌 모아 태산

www.acmicpc.net/problem/10844

2차원 배열 dp[x][y]에 sol[x][y]의 결과를 저장하고

이미 방문하여 계산을 마친 [x,y] 는 사전에 저장해놓은 dp[x][y]를 사용하여 계산해 반복 계산을 줄인다.

계단 수의 경우의 수는 한칸 아래 혹은 한칸 위 뿐이므로 가장 작은 수 0과 가장 큰 수 9를 예외로 두고

if (x == 0)
dp[x][y] += sol(x + 1, y + 1);
else if (x == 9)
dp[x][y] += sol(x - 1, y + 1);
else {
dp[x][y] += sol(x - 1, y + 1);
dp[x][y] += sol(x + 1, y + 1);
}

다음과 같은 형식으로 재귀 형태로 구성하며

if (y == n - 1) {
dp[x][y] = 1;
return dp[x][y];
}

가장 높은 자릿수에서는 더이상 반복하지 않고 1 을 return 한다.

코드

#include<iostream>
#define MAX 101
#define N 10

using namespace std;
long long dp[N][MAX] = { 0 };
int n;

long long sol(int x, int y) {
	//이미 방문한 경우
	if (dp[x][y] != 0)
		return dp[x][y];
	//기저
	if (y == n - 1) {
		dp[x][y] = 1;
		return dp[x][y];
	}

	if (x == 0)
		dp[x][y] += sol(x + 1, y + 1);
	else if (x == 9)
		dp[x][y] += sol(x - 1, y + 1);
	else {
		dp[x][y] += sol(x - 1, y + 1);
		dp[x][y] += sol(x + 1, y + 1);
	}

	return dp[x][y] % 1000000000;
}


int main() {
	cin >> n;
	long long sum = 0;
	for (int i = 1; i < 10; i++)
		sum += sol(i, 0);

	cout << sum % 1000000000 << endl;
	return 0;
}

결과

www.acmicpc.net/problem/10942

칠판에 적혀 있는 숫자들을 arr 에 저장하고 2차원 배열 dp 를 통해 ( dp[s][e]  ( 질문이 S E 일 때의 결과) ) 결과들을 저장하여 이미 계산이 이뤄진 경우의 수를 반복 계산하지 않도록 한다.

펠린드롬을 검사할 때에는 첫번째 index와 마지막 index부터 하나씩 더하고, 빼면서 비교하여 체크한다.

코드

#include <iostream>
#include <string.h>

using namespace std;

int N;
int arr[2001];
int M;

int dp[2001][2001];

bool sol(int s, int e) {

	//이미 확인한 경우
	if (dp[s][e] != -1)
		return dp[s][e];

	//펠린드롬인지 검사
	bool answer = 1;
	for (int i = 0; i <= (e - s) / 2; i++)
	{
		if (arr[s + i-1] != arr[e - i-1]) {
			dp[s][e] = 0;
			answer = 0;
			break;
		}
	}
	dp[s][e] = answer;
	return answer;
}

int main() {

	ios::sync_with_stdio(false);
	cin.tie(0);

	for (int i = 0; i < 2001; i++) 
		memset(dp[i], -1, sizeof(int) * 2001);

	cin>>N;
	for (int i = 0; i < N; i++)
		cin>>arr[i];
	cin >> M;

	bool ans[1000000];

	int S, E;
	for (int i = 0; i < M; i++)
	{
		cin >> S >> E;
		ans[i] = sol(S, E);
	}

	for (int i = 0; i < M; i++)
	{
		cout<<ans[i]<<"\n";
	}

	return 0;
}

결과

www.acmicpc.net/problem/2104

분할 정복을 통해 해결

1. mid 를 중심으로 왼쪽 부분배열의 최대값

2. mid 를 중심으로 오른쪽 부분배열의 최대값

3. mid를 포함한 부분배열의 최대값

중 가장 큰 값을 출력

#include <iostream>
#include <algorithm>

using namespace std;

const int MAX = 1000001;

int N;
int A[MAX];

long long GetMax(int from, int to)
{
	if (from == to) return (long long)A[from] * A[from];

	int mid = (from + to) / 2;
	//1. 왼쪽 부분배열의 최대값
	long long leftSum = GetMax(from, mid);
	//2. 오른쪽 부분배열의 최대값
	long long rightSum = GetMax(mid + 1, to);

	//1+2.왼쪽, 오른쪽 부분배열의 최대값
	long long maxValue = max(leftSum, rightSum);

	
	int left = mid;
	int right = mid + 1;

	long long sum = A[left] + A[right];
	long long minValue = min(A[left], A[right]);
	// 최대 값 비교

	maxValue = max(maxValue, sum * minValue);

	//3. mid를 포함한 부분배열의 최대값
	while (left > from || right < to)
	{
		//값이 더 큰 방향으로 이동하면서 최대값을 찾음
		if (right < to && (left == from || A[left - 1] < A[right + 1]))
		{
			sum += A[++right];
			minValue = min(minValue, (long long)A[right]);
		}
		else    
		{
			sum += A[--left];
			minValue = min(minValue, (long long)A[left]);
		}
		long long crossSum = sum * minValue;
		// 한 칸씩 이동하면서 구한 최대값과 현재최대값 비교 후 저장
		maxValue = max(maxValue, crossSum);
	}

	//1+2+3 . 세 가지 경우 중 최대값을 구하여 저장
	return maxValue;
}

int main()
{
	cin.tie(0);
	ios::sync_with_stdio(false);

	cin >> N;
	for (int i = 1; i <= N; i++) cin >> A[i];

	cout << GetMax(1, N);

	return 0;
}

www.acmicpc.net/problem/1725

분할정복을 통해 문제를 해결하였다.

문제에서 middle(중단점) 을 기준으로 히스토그램을 나누었을 때 최대값이 나올 수 있는 경우는 세가지이다.

1. middle을 중심으로 왼쪽부분에 최대값이 있는 경우

2 middle을 중심으로 오른쪽부분에 최대값이 있는 경우

3. middle을 포함하여 직사각형을 이루고 있는 경우

한 기둥을 중심으로 최대값의 넓이를 계산하기 위해서는 더 높은 막대로 확장해나가면서 최대값과 비교하여 최종적으로 최대값을 구한다.

세가지 경우에 대하여 각각 최대값을 구하고 그 중 가장 큰 값을 출력한다.

#include<iostream>
#include<cmath>
#include<algorithm>

using namespace std;

int a[100001];

int maxSize(int start, int end) {
	if (start == end)return a[end];

	int mid = (start + end) / 2;
	int lo = mid, hi = mid + 1;
	int height = min(a[lo], a[hi]);
	int ret = height * 2, tmp;

	//start와 end를 기준으로 조건에 따라
	//한쪽 끝에 도달했을 경우 종료
	while (start < lo || hi < end) {
		if (start == lo) tmp = ++hi;
		else if (hi == end) tmp = --lo;
		//더 큰쪽으로 확장을 진행한다.
		else if (a[lo - 1] < a[hi + 1]) tmp = ++hi;
		else tmp = --lo;
		//1칸씩 확장하면서 현재까지의 최대값을 ret에 저장
		height = min(height, a[tmp]);
		ret = max(ret, height * (hi - lo + 1));
	}

	//1. 가운데에 걸치는 부분 배열, 2. 왼쪽 부분 배열 3. 오른쪽 부분 배열
	//세가지중 가장 큰 값을 return 한다.
	return max(ret, max(maxSize(start, mid), maxSize(mid + 1, end)));
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	int n; cin >> n;
	for (int i = 0; i < n; ++i)cin >> a[i];
	cout << maxSize(0, n - 1);
}

www.acmicpc.net/problem/1074

문제 해결

• 이전에 해결하였던 쿼드트리 문제와 동일하게 각각의 problem을 4개의 subProblem으로 나누어 해결하였다.
• 하지만 이 문제는 최대 2의 15승까지의 입력 값을 받기 때문에 크기 1의 subProblem를 모두 찾아서 위치를 비교하여 문제를 해결할 경우 시간초과가 난다.
• 그렇기 때문에 subProblem으로 들어왔을 때 만약 주어진 (r,c)가 현재 subProblem의 범위에 포함되어 있지 않은 경우에는 현재 subProblem에 포함되어 있는 개수 h* h를 출력값 answer에 더해주고 return 시켜서 더이상 현재 subProblem이 분할하여 재귀에 들어가지 않도록 하였다.
• 문제 해결순서는 현재 문제에서 주어진 Z 와 같은 이동 순서를 가지므로 최종 출력값이 마지막에 문제에 대한 답을 찾기 전까지의 모든 최하위 subProblem의 갯수와 동일하므로 문제가 발생하지 않는다.
• 최종적으로 주어진 c와 r에 해당하는 subProblem에서 현재 answer값의 출력하고 return하여 이후 과정에서 출력 값이 변화하는 것에 대한 문제를 해결하였다.

코드

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

using namespace std;

vector<int> check;
int N, r, c;
int answer = 0;

void solution(int h, int x, int y)
{
	//입력값으로 주어진 r과 c에 해당하는 subProblem에서 출력
	if (x == r && y == c){
		cout << answer << endl;
		return;
	}
	//c와 r이 현재 subProblem의 범위 내에 포함되지 않는 경우
	//현재 subProblem의 크기만큼 answer에 더해주고 return하여
	//더이상 재귀를 진행하지 않는다.
	if (r > x + h - 1 || c > y + h - 1 || r < x || c < y){
		answer += h * h;
		return;
	}

	solution(h / 2, x, y);
	solution(h / 2, x, y + (h / 2));
	solution(h / 2, x + (h / 2), y);
	solution(h / 2, x + (h / 2), y + (h / 2));
}

int main() {

	cin >> N >> r >> c;
	solution(pow(2, N), 0, 0);
	return 0;
}

결과

www.acmicpc.net/problem/1992

문제 해결

문제의 예제와 아래에 있는 입력과 출력 예제를 보고 나서 문제의 내용을 이해할 수 있었다.

• 입력에 따른 출력형식은 problem을 4개의 subProblem으로 나누고 크기가 1인 가장 하위 subProblem까지 갔을 때 부터 결정되기 시작한다.
• 상위 subProblem의 출력형식은 하위 4개의 subProblem이 통일되어 있는지, 다른지에 따라서 결정되기 때문이다.
• 입력은 항상 2의 제곱수로 이루어지기 때문에 1, 4, 8, 16... 등 크기가 1인 가장 하위 subProblem에서 return한다고 하였을 때 모든 입력을 4개의 subProblem으로 나누어 해결할 수 있다.

반례

0000

0101

0000

0101

다음과 같은 입력의 경우에는 4개의 subProblem의 return값이 모두 같아서

(0001) 로 출력이 되는 문제가 발생하였는데 문제의 조건에 따르면

((0001)(0001)(0001)(0001)) 이렇게 출력이 되어야 문제가 해결된다.

이를 해결하기 위해

if (compareString(req)&&(req[0]).size()==1)
      return req[0];

다음의 부분을 통하여 각각의 subProblem의 return값이 모두 동일하더라도 size가 1일 때만 하나로 통합되도록 하였다.

코드

#include<iostream>
#include<string>
#include<algorithm>
#include<vector>

using namespace std;

#define MAX 65

int N;
int image[MAX][MAX];
string str[MAX];
string answer;

bool compareString(vector<string> str) {
	bool check=true;
	for (int i = 1; i < str.size(); i++) {
		check = str[i - 1].compare(str[i]);
		if (check != 0)
			return false;
	}
	return true;
}

string solution(int h,int x,int y)
{ 
	//h가 1일 때 현재 index를 return
	if (h == 1)
		return to_string(image[x][y]);
	vector<string> req;
	req.push_back(solution(h / 2 ,x, y)); 
	req.push_back(solution(h / 2, x, y+(h / 2)));
	req.push_back(solution(h / 2, x+(h /2) , y));
	req.push_back(solution(h / 2, x+(h / 2), y+(h / 2)));
	
	//abcd가 다 같다면 한 개의 값만 뽑아서 그걸 print하는데 그 때는 ()를 쓰지않음
	//abcd의 값이 다 같은게 아니라면 ()를 쓰고 안에 내용들을 모두 프린트
	if (compareString(req)&&(req[0]).size()==1)
			return req[0];
	else
		return "("+ req[0] + req[1] + req[2] + req[3]+")";
}

int main()
{
	cin >> N;
	for (int i = 0; i < N; i++){
		string s;
		cin >> s;
		for (int j = 0; j < N; j++)
			image[i][j] = s[j] - '0';
	}
	cout << solution(N, 0, 0);
	return 0;
}

결과

• 입력된 값들 중 점수를 기준으로 정렬한 후에 같은 점수에 대하여 마감일 기준으로 정렬한다.
• 최대한의 점수를 가장 우선순위로 두고 마감일에 가장 가깝게 과제를 끝마치도록 한다.
• 언제 어떠한 과제를 할 지를 저장하는 array에 가장 높은 점수부터 해당 마감일에 과제를 완료하는 것으로 가정하여 array에 저장한다.
• 마감일이 같은 경우 마감일보다 작은 index 중에 지정되지 않는 array에 해당 과제를 저장한다.
• 모든 과제에 대하여 저장이 끝나고 array내에 지정되어 있는 점수의 합을 구하여 출력한다.

코드

#include<iostream>
#include<algorithm>
#include<vector>
#include<utility>

using namespace std;

int main()
{
	int N;
	int d;
	int w;
	int answer = 0;
	vector<pair<int, int>> Score;
	cin >> N;
	int array[1000] = { 0 };

	for (int i = 0; i < N; i++){
		cin >> d >> w;
		Score.push_back(pair<int, int>(w, d));
	}
	
	sort(Score.begin(), Score.end());

	for (int i = N-1; i >= 0; i--)
	{
		while(Score[i].second>-1)
		{
			if (array[Score[i].second - 1] == 0) {
				array[Score[i].second - 1] = Score[i].first;

				break;
			}
			else
				Score[i].second--;
		}
	}
	for (int i = 0; i < 1000; i++)
	{
		answer += array[i];
	}

	cout << answer << endl;

	return 0;
}

결과

문제 링크

• 주어진 P를 기준으로 V에 대하여 최소한의 나머지를 가질 때까지 나눈다.
• 해당 P마다 L일을 사용할 수 있으므로 나눈 몫에 L을 곱하여 사용하는 날로 정한다.
• 나눈 나머지에 대하여 L을 기준으로 비교하여 L보다 작거나 같은 만큼을 사용하는 날로 정한다.
• 사용하는 날을 모두 더하여 최대 며칠동안 사용할 수 있는지 출력한다.

L에 대하여 P를 기준으로 최대한 쉴 수 있는 날짜를 먼저 정한 후 나머지에 대하여 계산하는

그리디 알고리즘을 통하여 해결한 문제였다.

코드

#include<iostream>
#include<vector>

using namespace std;

struct inputData {
	int L;
	int P;
	int V;
};

vector<inputData> input;
int l, p, v;
inputData tmpInput;

int Solution(int i)
{	
	int tmp = input[i].V % input[i].P;
	if (tmp > input[i].L)
		return input[i].V / input[i].P * input[i].L + input[i].L;
	else
		return input[i].V / input[i].P * input[i].L + tmp;

}

int main()
{
	do  {		
		cin >> l>> p>> v;
		tmpInput.L = l;
		tmpInput.P = p;
		tmpInput.V = v;
		input.push_back(tmpInput);
	} while (l != 0 && p != 0 && v != 0);

	for (int i = 0; i < input.size() - 1; i++)
	{
		printf("Case %d: %d\n", i + 1, Solution(i));
	}
	return 0;
}

결과