문제 및 풀이

너 봄에는 캡사이신이 맛있단다 (https://www.acmicpc.net/problem/15824)

굉장히 난해해 보였으나, ‘모든 최대 - 최소의 합’ == ‘모든 최대의 합’ - ‘모든 최소의 합’이 성립한다는 것을 이해하면 풀이가 간단해진다. 전체 스코빌 지수를 정렬해 각각의 스코빌지수가 최대일 때의 값과 최소일 때의 값을 구해줄 수 있다.

참고: 2018 아주대학교 프로그래밍 경시대회 풀이 슬라이드

• [Code]
• 조합론 문제는 ‘구하고자 하는 값과 동치가 되는 더 계산하기 쉬운 형태’로 문제를 다르게 해석해 변경하는 신박한 문제가 종종 있는 것 같다.

불량 사용자 (Link)

조합의 결과가 중복될 수 있는 상황에서 조합을 만드는 과정에서 비트마스킹을 사용해 가지치기하면 빠르게 풀 수 있다.

1. user_id 기준으로 완전탐색하려면 제재 사용자에 해당되지 않는 경우도 있기 때문에 현재 단계에서 가지치기를 통해 다음 단계를 보지 않을 이유를 확정하기 복잡하다. 코드가 좀 더 지저분해진다.

   1. 제재 사용자에 포함되고 탐색 가능하다면 go()
   2. 제재 사용자에 포함되는데 다른 사용자 ID와 매칭돼서 현재는 사용 불가라면 return 0
   3. 제재 사용자에 포함되지 않는다면 다음 depth로 넘어가야 함 (전처리로 해결 가능)

2. banned_id는 반드시 1명 이상의 사용자가 포함되는 문자열이기 때문에, 완전탐색 기준으로 잡는다.

3. 어떤 걸 기준으로 하더라도 조합을 만들 때에 중복이 발생(A가 먼저 뽑히고 B가 나중에 뽑히고, 그 반대 가능)할 수 있어, 중복이 발생할 때 가지치기를 할 수 있으면 좋다. 만들어가는 과정 자체를 bit 를 써서 값을 만들 때 체크하며 바로 가지치기 가능하다.

   nextBit 의 check 로직에는 ‘현재 bit에 userIdx 가 포함돼 있는지, ‘nextBit 가 이미 탐색된 적 있는지 의 2가지 여부를 한 번에 조사할 수 있는 좋은 코드다. 이 방법으로 중복으로 발생하는 조합의 경우를 제거할 수 있다.

• [Code]