[백준] 23036. CAN WIN

newbieski·2021년 11월 5일
0

백준

목록 보기
40/210

https://www.acmicpc.net/problem/23036

요약

  • 부분합 / 길이 가 주어진 값 P보다 큰 경우의 수를 구하기

접근법

  • 일일이 합을 구하고 나누고의 아이디어에서 확장이 어려웠음
  • P의 값으로 x1, x2.... 하는 아이디어만 생각이 났지만 결국 완전탐색에서 벗어나지 못했음
  • 더하다보면 남는 것도 있고 부족한 것도 있고...에서 아이디어를 발전시켜서 "각각이 제 몫을 한다면?"으로 아이디어를 확장시킴
    • 각각의 숫자가 P보다 크면 제 몫을 한 것일 것임 => 남는 값이 있음
    • P 보다 작으면 제 몫을 못함 => 남는 값이 있으면 채우거나 해야함
  • 정리해보면 입력에서 P를 빼면서 얼마나 "잉여"가 남는지를 구하고
  • 잉여값끼리 더했을때 0보다 큰지를 확인하는 문제가 가능해짐
    • 주어진 수열에서 부분합이 0보다 큰 경우의 수를 구하는 접근법

누적합 접근법

  • 부분합이 0보다 큰 것을 구하는 접근법은 유사한 문제가 있었는데
  • 일단 누적합을 다 구해놓았을 때 i ~ j의 부분합을 구한다고 하면
  • sub[j] - sub[i - 1] 형태가 될 것임
  • sub[j]를 안다고 치면 sub[i - 1]이 sub[j]보다 작으면 구하려고 하는 값이 0보다 클 것임
  • 즉 j 보다 작은 범위에서 sub[j] 보다 작은 값들의 수 ==> 구간 트리

좌표 압축

  • 누적합의 값이 큼 => 구간트리로 표현이 어려움
  • 누적합이 나오는 경우의 수는 N
  • N개의 숫자에 대해서 "서열"은 판단 가능 -> relabeling
  • 즉 sub[j] 보다 작은 값들의 수를 판단 가능함. sub[j]를 relabeling 했을때 k라고 하면 k 보다 작은 것들의 개수를 세면 됨

구현

  • 입력을 받아서 P를 빼고, 누적합을 구해나감
  • 누적합을 relabeling 함
  • 다시 누적합의 시작부터 진행을 해나가는 데 할 일은
    • sub[i] 보다 작은 것들의 경우의 수를 구해서 answer에 더함 => segsum(1 ~ sub[i])
    • sub[i]가 나타난 빈도수를 +1함 => segupdate(sub[i], +1)
    • sub[i]의 좌표압축값 사용, 구간트리 사용
profile
newbieski

0개의 댓글