글 읽기 - 2647 질문입니다.

lyzqm 6년 전 1

알고리즘이 틀린건지 구현이 틀린건지 모르겠네요.

스택을 이용했는데 스택이 비어있거나 top이 현재 위치와 같은색이면 push해주고

나머지는 pop해주면서 구간에서 가장 높은위치를 구해서 답을 구해줬는데요.

20%에서 틀렸다고 나오네요.

도와주세요

#include <cstdio>
#include <stack>
#include <vector>
#include <algorithm>
using namespace std;
int N;
char input[101];
stack<pair<int, bool>> stk;
int save[101];
vector<pair<int, int>> v;
// 1- black, 0- white
int main() {
	scanf("%d", &N);
	scanf("%s", &input);

	int ans = 0;
	for (int n = 1;n <= N;n++) {
		int here = input[n - 1] - '0';
		if (stk.empty() || stk.top().second == here) {
			stk.push({ n, here });
		}
		else {
			int ma = 0;
			int l = stk.top().first, r = n;
			stk.pop();
			if (l > r) swap(l, r);
			for (int n = l + 1;n <= r;n++) {
				ma = max(ma, save[n]);
			}
			ma += 1;
			ans += ma * 2 + r - l;
			for (int m = l + 1;m <= r;m++) {
				if (save[m] < ma) save[m] = ma;
			}
			v.push_back({ l, r });
		}
	}
	sort(v.begin(), v.end());
	printf("%d\n", ans);
	for (auto &n : v) {
		printf("%d %d\n", n.first, n.second);
	}
	return 0;
}

QuqqU 5년 전 0

이거 그리디로는 안풀리나요...?

lyzqm 5년 전 2

dp로 풀어야 되는거 같습니다

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

2647 질문입니다.

lyzqm 6년 전 1

QuqqU 5년 전 0

lyzqm 5년 전 2

Baekjoon Online Judge

채점 현황

문제

유저 대회 / 고등학교 대회

출처

대학교 대회

도움말