chris2tg   2년 전

결과적으로 맞긴 했는데 

틀린 코드에서 과정상 반례가 있는지 잘 모르겠어서 질문드립니다.

코드가 좀 더러워도 양해부탁드립니다.

각 brick마다 개수를 처음에 조사한 다음,

priority queue에 pair을 {개수,종류}로 집어넣으면 개수 크기대로 뽑혀 나오는데

before이라는 변수에 바로 전에 뽑았던 brick 종류를 저장해놓고 같은걸 뽑았으면 그 다음 것을 뽑고 원래 것을 다시 넣어놓습니다.

이러다가 두 가지 경우 중 하나면 while loop을 종료하는데

  1. 1 1 1 1 1 1 1 이런식으로 개수가 1개짜리 블록이 여러 종류가 있을 때
  2. 두 종류의 블록이 남아 있을 때

이 때 마지막 블록이 q가 되도록, 그리고 인접한 블록에 같은 블록이 오지 않도록 할 수 있는지를 체크하고 그렇게 되도록 ans에 블록 배열을 집어넣습니다.

그런데 q가 웬만하면 가장 나중에 뽑히는 게 좋기는 하니 ac를 받을 때는 q에 해당하는 블록을 다 0으로 바꾸고 출력할 때만 q로 보이도록 했습니다. (동일 개수일 때는 블록 이름이 작아야 늦게 뽑히기 때문)

그런데 처음에는 이 조건을 넣지 않고 문제를 풀었는데 11% 부근에서 틀렸습니다 가 나옵니다.

즉 q를 가장 낮은 번호 취급을 안했을 때 배열을 못 만드는 반례가 있다는 뜻인데 아무리 찾아보아도 이러한 예시가 있는지 모르겠습니다.

감사합니다.

코드는 맞은 코드를 첨부했는데 이 코드에서 q를 0으로 바꾼 부분들이 없다고 생각하면 질문의 틀린 코드입니다.

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