lyzqm   2년 전

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

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

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

어디부분이 틀렸을까요?

chogahui05   2년 전

반례 TC에 대한 답 : 3

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

BBBBBBAB


(2) 6번째를 B로

BBBBBBBB


(3) 모두 바꾼다

AAAAAAAA


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


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

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



chogahui05   2년 전

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

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


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

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


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

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

lyzqm   2년 전

제가 푼 알고리즘이 최적값이 아닌것 같긴했는데 이런 반례가 있었군요..
감사합니다 가희님!

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