[백준] 25336. K-균형 잡힌 수

newbieski·2022년 9월 14일
0

백준

목록 보기
168/210

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

문제 요약

  • 길이가 10^5인 숫자 X가 주어짐
  • X이하인 K 균형잡인 수를 구하기
  • K 균형잡인 수 : 각 숫자별 등장 횟수 "최대 - 최소" <= K인 숫자

접근법

  • 숫자가 엄청 큼. 테스트 케이스도 있지만 일단 모든 X 길이의 합은 10^5임
  • 주어진 숫자가 K 균형잡인 숫자면 바꿀 필요는 없음
  • 여러가지 단서를 찾아서 그리디한 접근으로 정답을 만들어 나갈 것임

단서1 - 낮은 자리부터 바꾸는 것이 유리

  • 만약에 숫자를 바꿔야한다면.. 1의 자리부터 바꾸는 것이 유리할 것임
  • 일단 어떤 자리를 바꾼다고 생각해보면 다음과 같음
    • ......7..... => ......6.....과 같이 바꾼다고 보면
    • 6 아래의 숫자들은 모든 숫자가 가능함, 심지어 .....69999 로 바꾸어도 원래 숫자보다는 작음. 왜냐하면 7->6으로 바뀌었으니까.
    • 바꾼 자리 이하는 "리셋" 된다는 느낌
  • 낮은 자리부터 바꿨다고 치고 가능한지 안 가능한지 따져볼만함
  • 더 큰 자리에 나온 등장 횟수는 새로 계산하지 않고 유지해나갈 수 있음
  • 숫자의 길이(10^5) x 바꿔보는 수(0~9) x 확인하는데 드는 비용 정도의 시간이 소요될 것임
  • 주의할 점은 최고 높은 자리 숫자가 0 이 되는 경우는 등장횟수 예외처리를 해주어야함 => 맨 앞자리 0은 카운팅하면 안됨

단서2 - 가능한지 가능하지 않은지 판단할 수 있음

  • 특정 자리를 바꾼다고 치면 다음의 정보를 얻을 수 있음
    • 상위자리 ~ 특정자리까지 숫자들의 등장 횟수 => cnt 변수를 잘 업데이트 하면 해결되는 문제
    • 내가 사용가능한 횟수 => x 자리 이후는 어떤 숫자를 사용해도 됨. 내가 자유롭게 가용함
  • 이렇게 이용해볼 수 있음
    • 상위자리에 나온 최대, 최소를 알고 있음
    • 최대 - 최소 <= k 이하여야하므로, 일단 아무리 작은 등장 횟수더라도 "최대 - k" 값은 가져야함
    • 예를 들어 "3"의 등장횟수가 6이었고, 조건을 만족하기 위해서는 11은 되어야하는데, 내가 가용한 횟수가 20이라고 하면, 20에서 5회는 "3"으로 사용할 수 있음
  • "최대 - k"가 안되는 것들의 조건을 주어진 가용 횟수로 모두 만족시킬 수 있으면 어쨋든 가능은 한 것임. 혹시 다 만족하고도 가용횟수가 남아도 문제가 되지 않음. 1 <= K 이기 때문에 어떻게 하든 차이가 1이상으로 나게 만들 수는 있음. (이건 곰곰히 생각해보면 됨)

단서3 - 일단 뒷 자리를 채울 숫자별 등장횟수를 알아냈다면 내림차순 정렬하면 됨

  • 당연히 9부터 뒷자리를 채우는 것이 유리함. 9999...도 되는데 9988..은 당연히 될 것임

단서4 - 기본적으로 등장횟수의 "최소값"은 맞춰 놓아야함

  • 특정 자리의 숫자를 바꾸었을대 "가능은 하겠다"라고 확인했을때 먼저 해야할 일임
  • 최대 - 최소 = K가 되어야하므로, 일단 최소값에 못 미치는 것들은 채워놓아야함
  • 가용한 횟수로 "최대 - k"가 안되는 등장횟수를 채워봄
  • 이때 등장하지 않은 것들은 채울 필요가 없음

단서5 - 가장 큰 수부터 사용을 할 수 있는지 판단해봄, 9를 예로 들어봄

  • 9가 등장을 안한 경우 => "최대 - k"로 채울 수 있는지 판단해봄
  • 9가 등장을 한 경우 => "최대 - k" 이상으로 채웠을 것임
  • 9가 채워졌을 경우 => "최대"로 채울 수 있는지 판단해봄
  • 9가 최대인 경우 => 최대를 더 늘릴 수 있는지 판단해봄. 최대 - 최소 = k일때까지 늘려볼 수 있음
  • 9가 최대이고 한계까지 늘려있는 경우 => 더 늘릴 수 있는지 판단봄. 9를 +1하고, 최소인 것들을 +1 했을때 가용한 횟수로 가능한지 판단해봄
  • 최대 한계를 안될때까지 계속 늘려봄

단서6 - 다음 큰 수(8), 다 다음 큰수(7) 에 대해서도 반복해서 판단해봄

시간 복잡도

  • 숫자의 길이(10^5) x 바꿔보는 수(0~9) x 확인하는데 드는 비용 + 최적값을 찾는데 드는 비용
  • 확인하는데 드는 비용 : 0 ~ 9 카운팅을 계속 확인할 것임 => 10
  • 최적 값을 찾는데 드는 비용 : 최악의 경우 +1 하고 카운팅 확인하고, +1하고 카운팅 확인하고 ... => 숫자의 길이 x 10
  • 결국 10^5 x 10 x 10 = 10^7 정도의 연산 횟수가 필요할 것임
profile
newbieski

0개의 댓글