글 읽기 - greedy 반례를 모르겠습니다

lyzqm 6년 전 0

A배열에는 A개수를 누적해 놓았고

ans에는 B의 개수를 일일이 세어놓은것과 전체를 한번뒤집고 난후의 B의 개수를 세어놓은것 중 작은것으로 초기화해줬습니다.

반복문으로 [0, n-1]까지 뒤집은 후(+1)의 B의 개수(lb) + [n, N-1]까지 B의 개수(rb)를 구해서 최솟값을 구해줬습니다.

어디부분이 틀렸을까요?

#include <cstdio>
#define min(a,b) ((a)<(b)?(a):(b))
int N;
char str[1000001];
int A[1000001];
int main() {
	scanf("%d", &N);
	scanf("%s", &str);
	for (int n = 0;n < N;n++) {
		A[n] += (n == 0 ? 0 : A[n - 1]) + (str[n] == 'A' ? 1 : 0);
	}
	int ans = min(N - A[N - 1], 1 + A[N - 1]);
	for (int n = 1;n < N;n++) {
		int rb = N - n - (A[N - 1] - A[n - 1]);
		int lb = A[n - 1];
		ans = min(ans, rb + lb + 1);
	}
	printf("%d\n", ans);
	return 0;
}

chogahui05 6년 전 0

반례 TC에 대한 답 : 3

(1) 1부터 3까지를 모두 바꾼다.

BBBBBBAB

(2) 6번째를 B로

BBBBBBBB

(3) 모두 바꾼다

AAAAAAAA

lyzqm님이 질문하신 코드가 출력하는 답 : 4

이 문제 조금 고민하다가 제 풀이가 맞나 검증 TC를 만들어서 확인해 보니..

제가 생각했던 풀이 역시 이런 TC에서 완전히 잘못된 값이 나오더라고요. 쉽지 않은 문제 같긴 하네요..

8
AAABBBAB

chogahui05 6년 전 0

ans에는 B의 개수를 일일이 세어놓은것과

전체를 한번뒤집고 난후의 B의 개수를 세어놓은것 중 작은것으로 초기화해줬습니다.

반복문으로 [0, n-1]까지 뒤집은 후(+1)의 B의 개수(lb) + [n, N-1]까지 B의 개수(rb)를 구해서 최솟값을 구해줬습니다.

뒤집음이 1번만 일어난다면 모르겠는데.. 그렇지 않습니다.

그렇기 때문에 아래 TC 같은 경우에도

4번 뒤집어 버리는 게 최적이 되어버리죠.

27
AAAAAABBBBBBBBBAAAAAABBBBBB

lyzqm 6년 전 0

제가 푼 알고리즘이 최적값이 아닌것 같긴했는데 이런 반례가 있었군요..

감사합니다 가희님!

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

문제

문제

출처

ICPC

greedy 반례를 모르겠습니다

lyzqm 6년 전 0

chogahui05 6년 전 0

chogahui05 6년 전 0

lyzqm 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말