순열과 조합 - 점층 처리

• 선택 전 처리
  • 백준 15812 침략자 진아
  • 백준 16949 벽 부수고 이동하기 4
• 점층 처리(선택지간 독립) => undo 필요(undo가 간편해야)
  • 백준 14500 테트로미노
  • 백준 14889 스타트와 링크 2 ^ 20 * 20 = 20971520
  • 백준 15661 링크와 스타트 스타트와 링크 2 ^ 19 * 20 = 10485760
  • 백준 15683 감시
  • 백준 15686 치킨 배달
  • SWEA 2112 보호 필름
• 선택 후 처리(선택지간 의존)
  
  • 백준 15684 사다리 조작(누적 불가 = 부분 처리 의미 없음) 
  • 백준 14502 연구소(선택횟수가 3번 고정, 부분 처리 의미 없음) C(64,3) * 8 * 8 = 2,666,496
  • 백준 17142 연구소3(선택지간 중첩 가능) C(10,r) * 50 * 50 = 630,000
  • 백준 17281 ⚾

BFS는 점층 불가

 

이러한 문제들은 하나의 조합에 대한 처리량이 많다. 

보호필름 : O(K*M)

링크와 스타트 : O((N/2)^2) : n명 조합할 때는 (n - 1)명 조합했을 때의 능력치에 n개의 S[i]개를 더해줘야 한다. -> 계차가 O(N), 일반항은 O(N^2)꼴

하나의 조합에 대한 처리는 이전 수준의 조합에서의 처리 결과에 marginal한 처리만 해주면 된다.

 

조합 문제에서는 각 조합에 대한 처리 연산량이 O(1) 또는 O(N)이면 next_permutation을 쓰되, 초과하면 DFS, BF를 쓸 것!