[BAEKJOON] 2240, 6198, 15681

※ 소스코드는 각 문제 설명 하단에 <더보기>를 통해 확인하실 수 있습니다.

 

[gold5, 2240 자두나무] - 다이나믹 프로그래밍(DP)

T초동안, 어떤 위치에서, 몇번이나 움직이며 자두를 받아가는지를 확인해야한다
즉, "dp[T 초에][W 만큼 움직이면][1/2 번 위치에서] = 자두를 받는다"로 볼 수 있고
T초가 지나갈 때 자두는 현재 위치에서 움직일지, 움직이지 말지 선택할 수 있다

 

이를 통해 유도할 수 있는 점화식은
  
1번나무에는 1초전 움직이지 않은 1번나무와, 2번나무에서 움직였을 때를 비교하고
dp[T][W][1] = max(dp[T-1][W][1], dp[T-1][W-1][2]); 
 
2번나무에는 1초전 움직이지 않은 2번나무와, 1번나무에서 움직였을 때를 비교할 수 있다
dp[T][W][2] = max(dp[T-1][W-1][1], dp[T-1][W][2]);
 
이후, 주어지는 자두의 나무위치에 따라 +0/+1을 진행하면 된다
또한, 움직이지 않는 경우 위 점화식을 대입하면 -1 idx에 접근하기 때문에 따로 관리한다
 
자두의 첫 시작 위치는 1이기 때문에, 1초에 자두를 받을 수 있는 경우를 초기화 해주어야 하는데
1번나무에 떨어지는 경우, 움직이지 않은 상태이므로 dp[1][0][1] = 1, (2번나무에 떨어지는 경우엔 0)
2번나무에 떨어지는 경우, 무조건 1번 움직여야 받을 수 있기 때문에 dp[1][1][2]만 신경써주면 된다(1번나무에 떨어지는 경우엔 0)

#include <iostream>
#pragma warning(disable:4996)

using namespace std;

int T, W;
int jadu[1001];
int dp[1001][31][3];
int main() {
	scanf("%d %d", &T, &W);
	for (int i = 1; i <= T; i++) {
		scanf("%d", &jadu[i]);
	}
	dp[1][0][1] = jadu[1] == 1 ? 1 : 0;
	dp[1][1][2] = jadu[1] == 2 ? 1 : 0;
	for (int t = 2; t <= T; t++) {
		for (int w = 0; w <= W; w++) {
			if (w == 0) {
				int idx = jadu[t] == 1 ? 2 : 1;
				dp[t][0][idx] = dp[t - 1][0][idx];
				dp[t][0][jadu[t]] = dp[t - 1][0][jadu[t]] + 1;
			}
			else {
				if (jadu[t] == 1) {
					dp[t][w][1] = max(dp[t - 1][w][1] + 1, dp[t - 1][w - 1][2] + 1);
					dp[t][w][2] = max(dp[t - 1][w - 1][1], dp[t - 1][w][2]);
				}
				else {
					dp[t][w][1] = max(dp[t - 1][w][1], dp[t - 1][w - 1][2]);
					dp[t][w][2] = max(dp[t - 1][w - 1][1] + 1, dp[t - 1][w][2] + 1);
				}
			}
		}
	}
	int answer = 0;
	for (int w = 0; w <= W; w++) {
		answer = max(answer, max(dp[T][w][1], dp[T][w][2]));
	}
	printf("%d", answer);
}

 

 

[gold5, 6198 옥상 정원 꾸미기] - 스택

2중 for문으로 하는 경우 O(N^2)으로 80000^2=64억 이므로 가뿐히 1초를 넘어가기에, 스택을 활용해주어야 한다
 
현재높이보다 작은높이는 추가하고
현재높이보다 큰높이가 들어온다면, 큰높이를 기준으로 기존의 작은높이들을 없애며 내림차순을 유지한다

이때, 유지된 스택은 항상 높은건물에서 → 낮은건물로 시야를 확보하고 있게 되며
다른 빌딩의 옥상을 확인할 수 있는 빌딩의 수는 (스택의 크기 - 1)이 된다. 
→ 건물이 1개인 경우, 바라볼 수 있는 건물이 없으므로 1 - 1 = 0
→ 건물이 3개인 경우, 바라볼 수 있는 건물이 A-B, B-C로 3 - 1 = 2가 됨을 알 수 있다

#include <iostream>
#include <stack>
#pragma warning(disable:4996)

using namespace std;

#define ll long long

int main() {
	int N, next;
	scanf("%d", &N);

	stack <int> s;
	ll answer = 0;
	for (int i = 0; i < N; i++) {
		scanf("%d", &next);
		if (s.empty()) s.push(next);
		else {
			while (!s.empty() && s.top() <= next) {
				s.pop();
			}
			s.push(next);
		}
		answer += s.size() - 1;
	}
	printf("%lld", answer);
}

 

 

[gold5, 17609 회문] - 문자열

문자열의 양끝을 포인트로 잡고 동일한지 비교하여 회문인지 확인한다
동일하지 않을 때, 해당 문자를 삭제하여 한번 더 비교하여 유사회문인지 확인한다

#include <iostream>
#pragma warning(disable:4996)

using namespace std;

int N;

int findPesudo(string str) {
	int len = str.length();
	int st = 0, ed = len - 1;
	while (st < len / 2 && st != ed) {
		if (str[st] != str[ed]) return 2;
		st++; ed--;
	}
	return 1;
}
int findPalindrome(string str) {
	int len = str.length();
	int st = 0, ed = len - 1;
	while (st < len / 2 && st != ed) {
		if (str[st] != str[ed]) {
			int leftRes = findPesudo(str.substr(st + 1, ed - st));
			int rightRes = findPesudo(str.substr(st, ed - st));
			
			if (leftRes == 1 || rightRes == 1) return 1;
			else return 2;
		}
		st++; ed--;
	}
	return 0;
}
int main() {
	scanf("%d", &N);
	string str;
	for (int i = 0; i < N; i++) {
		cin >> str;
		printf("%d\n", findPalindrome(str));
	}
}