글 읽기 - 반례가 있을까요?

hy2850 2년 전 0

ABC 혹은 ACB 패턴으로 세 팀이 모여있는 경우를 만들 때, 일치하지 않는 사람 수를 세는 슬라이딩 알고리즘을 구현했습니다.

ex) team = "AABAC" : A 셋, B 하나, C 하나
AAA B C
AAA C B
team += team 해서, 원형 상태를 펴서 직선으로 나열해줍니다.
이후 위 패턴과 일치하는지, 일치하지 않는다면 몇 명의 사람을 바꿔줘야 하는지 세서 최솟값을 계속 업데이트 해줍니다.

n = 1, 2, 3, 100000등의 edge case 직접 다 만들어서 체크해봤고,

직접 슬라이딩 알고리즘이 제대로 작동함을 체크했는데 WA가 뜹니다.

혹시 반례가 있을까요?

from collections import Counter

n = int(input())
teams = list(input())

cnt = Counter(teams)
a_cnt = cnt['A']
b_cnt = cnt['B']
c_cnt = cnt['C']

abc_cnt = [teams[0 : a_cnt].count('A'), teams[a_cnt : a_cnt + b_cnt].count('B'), teams[a_cnt + b_cnt : ].count('C')]
acb_cnt = [teams[0 : a_cnt].count('A'), teams[a_cnt : a_cnt + c_cnt].count('C'), teams[a_cnt + c_cnt : ].count('B')]
"""
원순열 : 3가지 팀 배열하는 순열 / 원에 놓을때 중복되는 경우의 수
= 3!/3 = 2가지
ABC ACB 
"""

min_ask = n # init : ask all people to move
teams += teams # stretch circle for sliding window

for i in range(n):
	abc_ask = [a_cnt - abc_cnt[0], b_cnt - abc_cnt[1], c_cnt - abc_cnt[2]]
	acb_ask = [a_cnt - acb_cnt[0], c_cnt - acb_cnt[1], b_cnt - acb_cnt[2]]
	min_ask = min(min_ask, sum(abc_ask), sum(acb_ask))

	#print(f"{i}th trial : {abc_cnt} , {acb_cnt}; min {min_ask}")

	if teams[i] == 'A':
		abc_cnt[0] -= 1
		acb_cnt[0] -= 1

	if teams[i+a_cnt] == 'A':
		abc_cnt[0] += 1
		acb_cnt[0] += 1
	elif teams[i+a_cnt] == 'B':
		abc_cnt[1] -= 1
	elif teams[i+a_cnt] == 'C':
		acb_cnt[1] -= 1

	if teams[i+a_cnt+b_cnt] == 'B':
		abc_cnt[1] += 1
	elif teams[i+a_cnt+b_cnt] == 'C':
		abc_cnt[2] -= 1

	if teams[i + a_cnt + c_cnt] == 'C':
		acb_cnt[1] += 1
	elif teams[i + a_cnt + c_cnt] == 'B':
		acb_cnt[2] -= 1

	if teams[i+n] == 'B':
		acb_cnt[2] += 1
	elif teams[i+n] == 'C':
		abc_cnt[2] += 1

print(min_ask)

ks2515 2년 전 1

이 글에서 아이디어를 얻어서 통과했습니다.

이미 푸셨는지는 모르겠지만, 혹시 아직 푸시지 못하셨다면 도움이 되길 바라는 마음으로, 랜덤으로 입력을 만든 다음 이 코드와 제 정답코드의 결과를 비교해서 출력이 다른 걸 체크하는 방식으로 반례를 만들어왔습니다.

12
AABBCCCABCAA

출력: 4, 정답: 3

12
BBCAAABBABCC

출력: 5, 정답: 4

9
BCCAACCBB

출력: 4, 정답: 3

7
CCCBCAC

출력 :2, 정답: 1

6
CCBCAA

출력 :2, 정답: 1

5
BCBAB

출력 :2, 정답: 1

7
CBCAAAA

출력 :2, 정답: 1

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

문제

문제

출처

ICPC

반례가 있을까요?

hy2850 2년 전 0

ks2515 2년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말