이것 저것 &

문제링크:www.acmicpc.net/problem/12904

(1 ≤ S의 길이 ≤ 999, 2 ≤ T의 길이 ≤ 1000, S의 길이 < T의 길이)

문자열의 범위가 위와 같으므로 재귀함수를 사용해 구현하면 시간 초과입니다.

S를 통해서 T를 만드는데 이때 T를 통해서 S를 유추하면 더욱 쉽다는 것을 아는지 모르는지에 따라서 난이도가 크게 달라지는 문제입니다.

T에서 두가지 규칙에 의해서 S문자열의 길이와 같아지게 될때 까지 반복하면 S를 통해서 T를 만들 수 있는지 여부가 결정되기 때문입니다.

구현자체의 난이도는 하,  문제 해결 아이디어가 중상..

아래는 정답코드입니다. 코드로 보면 충분히 이해가 되실겁니다.

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


string s, t;
bool result = 0;


int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);

	cin >> s;
	cin >> t;


	while (1) {

		if (s.size() == t.size()) {
			if (s == t)
				result = 1;
			break;
		}
		
		if (t[t.size() - 1] == 'A')
			t.pop_back();
		else {
			t.pop_back();
			reverse(t.begin(), t.end());
		}
	}

	cout << result << endl;
}

문제링크: www.acmicpc.net/problem/2629

반례를 못찾아서 고생한 문제입니다.

양팔저울을 통해서 구슬의 무게를 잴 수있는지 확인하는 문제입니다. 모든 경우를 확인해주어야 합니다.

근데 이때 재귀를 사용하여 해결할 수 있고 dp를 활용하자는 생각을 가지는 것이 문제 접근의 핵심입니다.

첫 번째, dp구현하기

dp[i][j]는 i는 현재 무게, j는 탐색하는 추의 인덱스 입니다.

두 번째, 재귀 점화식 도출

모든 경우를 다 고려해야 합니다. 즉, 

ret = solved(abs(weight - sinker[i]), i + 1);
ret = max(ret, solved(weight, i + 1));
ret = max(ret, solved(weight + sinker[i], i + 1));

3가지를 고려해야 합니다.

이때 abs(weight - sinker[i]) 부분 때문에  고생했습니다.

저는 처음에 

if (sinker[i] <= weight) {
ret = solved(weight - sinker[i], i + 1);
}

이렇게 구현했습니다. 근데 이때 추보다 작은 무게가 먼저 들어올때 추를 사용하지 않고 넘어가다보니 오류가 났습니다.

해결하기위해서 2가지 방법이 있습니다.

1. 인덱스를 사용하기 

2. 그냥 절대값으로 해결하기

저는 2번을 선택했습니다. 절대값으로 고려하여도 저울의 어느쪽에 두는지의 차이이기 때문에 상관이 없습니다.

아래는 정답코드입니다.

코드를 천천히 따라가면서 이해해보세요

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>
using namespace std;
int a = 0, b = 0;
int sinker[31] = { 0, };
int arr[7] = { 0, };
int dp[100001][31];


int solved(int weight, int current) {
	if (weight == 0)
		return 1;
	if (current > a)
		return 0;

	int &ret = dp[weight][current];
	if (ret != -1)
		return ret;
	ret = 0;
	for (int i = current; i <= a; i++) {

		ret = solved(abs(weight - sinker[i]), i + 1);
		ret = max(ret, solved(weight, i + 1));
		ret = max(ret, solved(weight + sinker[i], i + 1));
		return ret;
	}
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	cin >> a;
	for (int i = 1; i <= a; i++)
		cin >> sinker[i];

	cin >> b;
	for (int i = 1; i <= b; i++) {
		int temp;
		cin >> temp;
		memset(dp, -1, sizeof(dp));

		
		if (solved(temp, 1))
			cout << 'Y';
		else
			cout << 'N';

		if (i != b)
			cout << ' ';
	}
	cout << endl;
	return 0;

}

문제링크:www.acmicpc.net/problem/4811

우선 규칙성을 찾으려고 노력했습니다. 그런데 규칙을 못찾았고, 자연스레 재귀함수를 사용한 dp인 up-down 방식으로 생각했습니다.

문제에서 주어지는 조건처럼 전체 알약, 반쪽 짜리 알약으로 구분하여 

dp[i][j]은 하나짜리 알약 i개가 있고 반쪽 짜리 알약 j개가 있을때 최대 경우의 수를 나타냅니다.

아래는 재귀함수 코드입니다.

long long solved(int whole, int half) {
	if (whole == 0)
		return 1;
	long long &ret = dp[whole][half];
	if (ret != -1)
		return ret;

	ret = solved(whole - 1, half + 1);

	if (half > 0)
		ret += solved(whole, half - 1);


	return ret;
}

만약 whole =0 이면 half만 남은 상태니까 결과값은 1!

그리고 모든 경우에서 whole -1 , half +1  호출

만약 half가 있다면 whole,half-1도 호출후 더하기

아래는 정답코드입니다.

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


long long dp[31][31];

long long solved(int whole, int half) {
	if (whole == 0)
		return 1;
	long long &ret = dp[whole][half];
	if (ret != -1)
		return ret;

	ret = solved(whole - 1, half + 1);

	if (half > 0)
		ret += solved(whole, half - 1);


	return ret;
}
int main() {

	ios_base::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);

	
	for (int i = 1; i <= 1001; i++) {
		memset(dp, -1, sizeof(dp));
		int temp;
		cin >> temp;
		if (temp == 0)
			break;
		cout << solved(temp, 0) << "\n";
	}

	return 0;
}

문제링크:www.acmicpc.net/problem/2533

어려웠습니다..ㅠㅠ

dp(up-down) 문제인건 인식했지만 우선 그래프를 어떤식으로 구현하고 dp를 구현할지 설계를 하는데 어려움을 겪었습니다.

• 1. 단방향 그래프 만들기
• 2. 그래프를 탐색하며 최소수 구하기

1. 우선 입력 받을때는 양방향으로 받고 재귀함수를 통해서 결과를 도출합니다.

void make_graph(int current, int parent) {
	if (parent != 0) {
		graph[parent].push_back(current);
	}
	
	for (int i = 0; i < vec[current].size(); i++) {
		if (parent == vec[current][i]) continue;
		make_graph(vec[current][i], current);
	}

}

parent 벡터에만 child 노드들을 넣어 놓음으로서 단방향 트리를 구현했습니다.

2. 그래프를 탐색하며 최소수 구하기는 일반적인 dp(up-down)과 흡사합니다. 

if (adapter) {
		ret = 1;
		for (int i = 0; i < graph[current].size(); i++)
			ret += min(solved(graph[current][i], adapter), solved(graph[current][i], !adapter));
	}
	else {
		ret = 0;
		for (int i = 0; i < graph[current].size(); i++)
			ret += solved(graph[current][i], !adapter);
	}

 1) 현재 노드가  얼리 어뎁터일때는 자식노드가  얼리 어뎁터일수도, 아닐수도 있습니다.

 2) 하지만 현재 노드가 얼리어뎁터가 아니라면  무조건 다음 노드는 얼리 어뎁터이어야 합니다.

2가지 조건을 통해서 재귀를 구현했습니다. 

아래는 정답코드입니다.

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


int n = 0;
vector <int> vec[1000001];
vector <int> graph[1000001];
int dp[1000001][2] = { 0, };

int solved(int current, bool adapter) {
	if (graph[current].empty()) {
		if (adapter)
			return 1;
		else
			return 0;
	}
	
	int &ret = dp[current][adapter];
	if (ret != -1)
		return ret;

	if (adapter) {
		ret = 1;
		for (int i = 0; i < graph[current].size(); i++)
			ret += min(solved(graph[current][i], adapter), solved(graph[current][i], !adapter));
	}
	else {
		ret = 0;
		for (int i = 0; i < graph[current].size(); i++)
			ret += solved(graph[current][i], !adapter);
	}

	return ret;

}

void make_graph(int current, int parent) {
	if (parent != 0) {
		graph[parent].push_back(current);
	}
	
	for (int i = 0; i < vec[current].size(); i++) {
		if (parent == vec[current][i]) continue;
		make_graph(vec[current][i], current);
	}

}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	cin >> n;
	for (int i = 0; i < n -1 ; i++) {
		int a, b;
		cin >> a >> b;
		vec[a].push_back(b);
		vec[b].push_back(a);
	}

	make_graph(1, 0);
	/*
	for (int i = 0; i < n; i++) {
		cout << graph[i].size() << endl;
	}*/

	memset(dp, -1, sizeof(dp));
	cout << min(solved(1, 0), solved(1, 1)) << endl;
	return 0;
}

문제링크:www.acmicpc.net/problem/18427

무난한 난이도의 dp 문제였습니다.

한 학생당 최대 1개의 블록라는 조건을 통해서 배낭문제 알고리즘으로 해결할 수 있습니다.

dp[i][j] 는 i번째까지 학생에게 j높이에서의 최대 경우의수라고 할때, 아래와 같이 됩니다. (초기화 작업으로 0일때는 1로 지정)

첫번째 학생이 2,3,5니까, dp[1]은 101101이 되고 두번째 학생을 포함하면 101203이되고... 

그러면 학생이 가진 블록뺀 dp[i-1][j-vec[i][k]] 만큼씩 더해주고 그 이후에 dp[i-1][j] 을 더해주면 해결됩니다.

조심할 점은  if (j >= vec[i][k]) 일때 dp[i - 1][j - vec[i][k]]을 수행하여야 한다는 점이다. 

아래는 정답코드입니다.

#include <iostream>
#include <string>
#include <vector>
using namespace std;

int n, m, h;
vector <int> vec[51];
int dp[51][1001] = { 0, };

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);

	cin >> n >> m >> h;
	cin.ignore(1);

	for (int i = 1; i <= n; i++) {
		string temp;
		getline(cin, temp, '\n');
		
		for(int j=0;j<temp.size();j++)
			if(temp[j]==' '||j==0)
				vec[i].push_back(stoi(&temp[j]));

			
	}
	

	
	//solve

	for (int i = 0; i <= n; i++)
		dp[i][0] = 1;

	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= h; j++) {
			
			
			for (int k = 0; k < vec[i].size(); k++) {
				
				if (j >= vec[i][k]) {
					dp[i][j] += dp[i - 1][j - vec[i][k]];
					dp[i][j] %= 10007;
				}
			}		
			dp[i][j] += dp[i - 1][j];
			dp[i][j] %= 10007;
		}
	}


	cout << dp[n][h] << endl;


	return 0;
}

문제링크:www.acmicpc.net/problem/2839

레전드 문제 설탕배달입니다....ㅋㅋㅋ

입문자분들이 가장 많이 풀고 절망을 느끼는 문제입니다.

오랜만에 다시 풀어봤는데 감회가 새로워서 포스팅합니다.

저의 예전 답입니다.

#include <stdio.h>
int main()
{
	int x = 0, y = 0, N = 0, resultx = 0, resulty = 0;
	int i = 0;
	int j = 0;
	scanf("%d", &N);
	for (x = 0; i <= N; x++)
	{
		i = 5 * x;
		for (y = 0; j <= N; y++)
		{
			j = 3 * y;
			if (i + j == N)
			{
				resultx = x;
				resulty = y;
			}
		}
		j = 0;
	}
	if (resultx == 0 && resulty == 0)
		printf("%d\n", -1);
	else
		printf("%d\n", resultx + resulty);
}

이중포문을 사용해서 구현했습니다.

5씩 증가하는 i와 3씩 증가하는 j의 모든 조합을 비교해보며 결과값을 도출하는 방법입니다. i가 j보다 상위 반복문에 있기 때문에 i가 최대가 되는 결과값이 최종적으로 resulty, x 에 저장이 되어지고 이를 통해 결과값을 얻습니다.

하지만 만약에 시간이나 데이터 크기가 더욱 커진다면 테스트를 통과하지 못할 확률이 있습니다.

예를 들어서 n=1000,000라면 해당 코드는 O(n^2)이므로 시간제한 1초를 훌쩍 넘게 됩니다.

이를 예방하기 위해서  반복문 하나만 써서 해결하는 방식도 생각해봤습니다.

	int answer = 0;
	int mod, num, result;
	num = n / 5;



	while (num >= 0) {

		mod = 0;
		result = 0;

		if (num > 0) {
			mod = n - 5 * num;
			result = num;
		}
		else {
			mod = n;
		}

		result += mod / 3;
		mod = mod % 3;

		if (mod == 0) {
			answer = result;
			return answer;
		}

		num--;

	}
	if (mod != 0)
		return -1;

	
		
	//return answer;

사실 같은 원리입니다. while문에서 5로 나눌수 있는 만큼 반복하며 진행합니다. 이때 5로 나눈 나머지만큼 3으로 다시한번 나눠보고 나머지가 0된다면 그대로 바로 결과를 출력하는 구조입니다.

사실은 2중포문을 사용할 필요가 없던 코드입니다. 

사실 구현하면서 고민을 꽤 많이 했던터라 아직도 많이 부족하다는 것을 느낄 수 있었습니다. 

더욱 열심히 해서 알고리즘 마스터가 되겠습니다. 

문제링크: www.acmicpc.net/problem/2616

down-up방식 점화식을 구하지 못해 up-down 방식을 사용했습니다.

한점 기준으로 해당 위치부터 소형 기관차를 사용하는 경우 혹은 사용하지 않는 경우 두가지를 비교해주며 결과값을 도출했습니다.

dp[i][j]는 i번째 위치에서부터  j개의 소형기관차를 사용할때 얻을 수 있는 최대값을 가르킵니다. 이때 점화식은

• max(solved(current + 1, cnt), solved(current + k, cnt + 1) + (arr[current + k - 1] - arr[current - 1])); 

아래는 정답코드입니다.

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

int n = 0, k = 0;
int dp[50001][3] = { 0, };
int arr[50001] = { 0, };

int solved(int current, int cnt) {

	if (current > n || cnt == 3)
		return 0;

	int &ret = dp[current][cnt];
	if (ret != -1)
		return ret;

	if ((current + k - 1) <= n)
		ret = max(solved(current + 1, cnt), solved(current + k, cnt + 1) + (arr[current + k - 1] - arr[current - 1]));


	return ret;
}



int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

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

	/*
	for (int i = 1; i <= n; i++)
		cout << arr[i] << endl;

	for (int i = 1; i <= n; i++) {
		for (int j = 0; j < 3; j++)
			cout << dp[i][j] << ' ';
		cout << endl;
	}*/
	return 0;
}

down-up방식도 가능할거 같아 찾아봤습니다.

lyzqm.blogspot.com/2017/03/2616.html

DP[N][M]=max(DP[N][M−1],DP[N−1][M−K]+S[M]−S[M−K] 해당 점화식 사용하셔서 푸는 답도 있습니다. 

문제링크: acmicpc.net/problem/2116

전형적인 구현문제입니다. 문제를 읽으면서 왤캐어렵지.. 생각했는데 

문제 조건중에 위 아래를 고정한 채 옆으로 90도, 180도, 또는 270도 돌릴 수 있다 라는 조건이 있어서 금방 접근 방법을 찾았습니다.

첫번째 값에서 시작할때 ~ 여섯번째 값에서 시작할때

총 6가지 경우 전부 확인해주어야 하는 브루트 포스입니다.

이때 1(a)번 위치는 6(f)번 위치와 2(b)번위치는 4(d)번위치와 3(c)번위치는 5(e)번 위치와 짝을 이루게 됩니다.

위아래가 되는 값들은 마킹을 해주고 나머지 값들을 통해서 결과값을 얻으면 됩니다. 

• 1. 위아래 값 마킹 
• 2. 결과값 비교

구현자체 난이도를 요하는 문제인데, 그 마저도 주사위에 익숙하시다면 어렵지 않으셨을 겁니다.

구현 문제는 꼭 설계를 꼼꼼하게 작성하고 진행하는 습관을 가집시다. (스스로에게 하는말)

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

int n = 0;
int arr[10001][7] = { 0, };
int result = 0;
int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	cin >> n;
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= 6; j++)
			cin >> arr[i][j];

	for (int i = 1; i <= 6; i++) {
		bool temp[10001][7] = { 0, };
		int num = 0, next = 0;

		for (int j = 1; j <= n; j++) {
			if (j == 1) {
				num = i;
				temp[j][i] = 1;
			}
			else {
				int val = next;
				for (int u = 1; u <= 6; u++) {
					if (val == arr[j][u]) {
						temp[j][u] = 1;
						num = u;
						break;
					}
				}
			}
		

			if (num == 1) {
				next = arr[j][6];
				temp[j][6] = 1;
			}
			else if (num == 2) {
				next = arr[j][4];
				temp[j][4] = 1;
			}
			else if (num == 3) {
				next = arr[j][5];
				temp[j][5] = 1;
			}
			else if (num == 4) {
				next = arr[j][2];
				temp[j][2] = 1;
			}
			else if (num == 5) {
				next = arr[j][3];
				temp[j][3] = 1;
			}
			else if (num == 6) {
				next = arr[j][1];
				temp[j][1] = 1;
			}
			
		}



		/*
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= 6; j++)
				cout << temp[i][j] << ' ';
			cout << endl;
		}*/

		int maxed = 0;
		for (int i = 1; i <= n; i++) {
			int temp_max_num = 0;
			for (int j = 1; j <= 6; j++)
				if (temp[i][j] == 0 && temp_max_num < arr[i][j])
					temp_max_num = arr[i][j];
			maxed += temp_max_num;
		}
		result = max(result, maxed);
	}


	cout << result << endl;

	return 0;
}