[백준] 22995. 증가하는 부분 수열의 개수 K

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

요약

• 증가하는 부분수열의 개수가 K인 수열을 만들며 됨
• ${1 <= K < 2^{18}, 만드는 수열의 길이 <= 34}$
• 공식 풀이 : https://github.com/justiceHui/Sunrin-Contest/blob/main/Sunrin-OI-2021/editorial.pdf

접근법

• 단순하게는 1, 1, 1, ... 처럼 만들어도 되지만 수열의 길이 제한조건을 만족시키지 못함
• 단조 증가 수열에서 증가하는 부분수열의 개수를 관찰해봄
  • 수열 : 1, 2, 3, 4, 5, 6, ...
  • 개수 : 1, 2, 4, 8, 16, 32, ....
• 누적합 + 지수 증가가 되면서 ${2^n}$ 형태로 값을 관찰할 수 있음
• K를 ${2^n}$ 들의 합으로 나타내는 방법을 고민해봄
  • 단순 1, 2, 4, 8, ... 들의 합만으로는 K를 표현하는데 한계가 있음 : ${1111...._{(2)}}$ 형태로 표현되기 때문임
  • 중간에 값을 한번 더 쓰면 0을 표현할 수 있음 예를 들어 ${1111_{(2)} + 100_{(2)} = 10011_{(2)}}$
  • 일단 K와 가장 가까운 1111...을 찾고, 나머지 값을 적절히 표현함
  • 이때 나머지 값은 구하려는 순열의 "뒤"에 적절히 배치함 => 서로간 영향이 없도록. 예시에서 4의 값의 변화를 관찰
    • 순열 : 1 2 4 2 2, 개수 : 1 2 4 2 2
    • 순열 : 1 2 2 2 4, 개수 : 1 2 2 2 8
  • ${K - 11111...._{(2)} = P}$