[백준] 22957. 짝수싫어수

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

요약

• 3, 5, 7로만 숫자를 만들어야함
• 3, 5, 7이 사용된 횟수가 모두 짝수이면 안됨
• 30자리 이하 숫자중에서 k 번째로 큰 숫자 구하기

접근법

• dp를 이용해서 경우의 수를 제거해 나가면서 k 번째 숫자를 찾는 방법
  • 7로 시작하는 경우의 수 < k 이면 일단 7로는 시작 안함
  • 5로 시작하는 경우의 수 > k 이면 5로 시작하고 그 이후를 봐야함
• 모두 짝수가 안되는 것의 처리
  • 전체에서 모두 짝수인 것을 제외하는 방법도 괜찮음
  • [길이][3이 홀/짝][5가 홀/짝][7이 홀/짝] = 경우의 수
  • 비트연산으로 [0/1][0/1][0/1] ==> [8]로 처리함
• 할 일
  • 몇 자리 숫자인지 파악해봄
    • n 자리일때 경우의 수?, n - 1자리일때 경우의 수?, ...
  • 자리수가 정해지면 가장 높은 자리의 숫자부터 채워 보면서 경우의 수를 체크함 : 7, 5, 3
  • (이전까지 사용한 7/5/3의 홀짝) + (앞으로 사용할 7/5/3의 홀짝) 이 짝이 되지 않는 것들의 경우의 수만 구해야함
    • 길이가 n인 경우를 구할때
    • 이전까지의 홀짝 정보가 (7/5/3 = 홀/홀/짝 = 1/1/0 = 6)이고
    • 가장 높은 자리가 7일때 경우의 수를 구해보면 ......7??????
    • 짝/홀/짝의 상태에서 길이가 n - 1인 모든 경우의 수
• 구현
  • dp[길이][홀짝정보]
  • f(홀짝정보, 길이) : 길이를 만족하는 전체 경우의 수에서 이전 홀짝정보와 연산하여 짝/짝/짝이 나오지 않는 것들의 합