[백준] 23046. 큰 수 뒤집기

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

요약

• 쿼리는 입력 문자열로 주어짐
• S를 갱신함(숫자를 추가하거나 뒤집거나)
• S가 표현하는 숫자들의 합을 구함
• 공식 해설은 여기에 있음 : https://www.youtube.com/watch?v=GopE8ImNugQ

접근법

• 숫자가 엄청 크기때문에 구해서 더하는 방법은 시도를 못함(복잡도, 큰 수 연산 등 걸림돌이 많음)
• 숫자 하나에만 집중을 해보면(첫 숫자) 차지하는 위치가 0, 1, 2, .... p 로 변하다가 뒤집어지면 어딘가로 가서 x, x + 1, x + 2... 로 변하다가 다시 뒤집어지면 p + 1, p + 2, ...로 변하다가 하는 규칙이 보임
• 뒤집어지는 경우가 발생하지 않는다면 첫 숫자는 0 ~ n - 1, 두번째 숫자는 0 ~ n ~ 2 이런식으로 위치할 것임
• 뒤집어지는 경우가 발생하더라도 다시 뒤집어지면 이전에 진행하던 상황을 "이어가게" 됨
• 즉 최초로 숫자가 주어지는 상황에서 앞으로 이 숫자가 어디 어디에 위치할지를 "예측"할 수 있음
  • 예측을 위해서 필요한 몇가지 정보가 있음
  • 뒤집고/다시 뒤집고 를 반영해서 앞으로 몇 개의 숫자들이 주어질지
  • 최초 시작위치는 어디가 될지 등등
• 특정 자리 수에(위치에) 숫자가 몇개 포함되는지를 구할 수 있음
  • +1 ~ -1 기법을 쓰면 예측한 위치에 기록을 해서 나중에 합하는 방식을 쓸 수 있음

구현

• 인덱스 판단 및 구현이 까다로움
• "-"로 나누어지는 블록단위로 합을 구해놓음
• 누적합을 구하는데 홀/짝별로 누적합을 구하고 끝에서부터 구해나감
  • 숫자가 최초로 등장하는 시점에 앞으로 언제까지 등장하는지를 구해야하기 때문에 누적합을 끝에서부터 구함
• 숫자가 최초 등장할때 다음의 두 가지 예측을 함
  • 최초 등장 : 0, 2번 뒤집, 4번 뒤집 .... 들의 합을 구함
    => 짝수번 뒤집으면 했던 과정을 계속 이어나가기 때문임
  • 한번 뒤집었을때 등장 : x, 3번 뒤집, 5번 뒤집....들의 합을 구함
    => 홀수번 뒤집었을때의 나타나는 위치는 연속일 것임
• 0의 자리부터 합을 구해나감
  • 1 ~ 9까지 나타나는 빈도수를 구하고
  • 빈도수 * 숫자로 합을 구하고
  • carriage를 더해서 자리수를 구함