백준 2877번: 4와 7

접근법

• 두 개의 수를 활용하는 문제이기 때문에 $2^n$과 관계가 깊습니다.
• 우선 몇 가지 경우를 나열해 보겠습니다.
  • 4,7
  • 44,47,74,77
  • 444,447,474,477,744,747,774,777
  • 4444,4447,4474,4477,4744,4747,4774,4777,7444,7447,7474,7477,7744,7747,7774,7777
• 이를 통해 몇 가지 규칙을 발견할 수 있습니다.
  • 길이가 n인 숫자는 $2^n$개 있습니다.
  • $2+4+8+...2^n = 2*(2^n-1)$ 를 통해 k번째 수의 길이를 구할 수 있습니다.
    • 0<k<=2인 k는 한 자리 수입니다.
    • 2<k<=2+4인 k는 두 자리 수입니다.
    • 2+4<k<=2+4+8인 k는 세 자리 수입니다.
    • 2+4+8<k<=2+4+8+16인 k는 네 자리 수입니다.
    • (2^(n+1))-2<=k<=(2^(n+2))-2인 k는 N자리 수입니다.
• 4자리 숫자를 다시 한번 살펴 보겠습니다.

• 1의 자리 숫자는 매번 바뀝니다.
• 10의 자리 숫자는 2번마다 바뀝니다.
• 100의 자리 숫자는 4번마다 바뀝니다.
• 1000의 자리 숫자는 8번마다 바뀝니다.

4자리 숫자 16개는 다음의 규칙을 가집니다 -> $10^t$자리 숫자는 $2^t$번마다 바뀝니다. (t는 4자리 숫자 내에서의 순서)

• 자리의 숫자가 바뀌는 규칙은 다음과 같이 적용될 수 있습니다.
  • 숫자를 1로 나눈 몫을 2로 나눈 나머지에 따라 값이 바뀝니다.
  • 숫자를 2로 나눈 몫을 2로 나눈 나머지에 따라 값이 바뀝니다.
  • 숫자를 4로 나눈 몫을 2로 나눈 나머지에 따라 값이 바뀝니다.
  • 숫자를 8로 나눈 몫을 2로 나눈 나머지에 따라 값이 바뀝니다.
  • 숫자를 2^(t-1)로 나눈 몫을 2로 나눈 나머지에 따라 값이 바뀝니다.

결론

• k번째 숫자가 몇 자리 수인지를 구합니다.(n)
• k번째 숫자가 해당 자릿수 숫자들 중 몇 번째로 등장하는지를 구합니다.(a)
  • 두 조건을 활용해 k번째 숫자를 알 수 있습니다.
  • k번째 수 = (2+4+8+...+n)+a

정답

k = int(input())

for n in range(0,100): #2^100은 10^9를 덮을 수 있는 충분히 큰 숫자입니다.
    # print(2**(n+1)-2,2**(n+2)-2)
    if 2**(n+1)-2 <= k-1 < 2**(n+2)-2:
        break

t = 2**(n+1)-2  #k는 n자리 숫자이며
a = k-t	#n자리 숫자 중 a번째에 등장합니다

reversed_answer = '' # 일의자리부터 계산하기 때문에 정답과는 반대로 값이 들어옵니다

#`숫자`를 `2^(t-1)`로 나눈 `몫`을 `2로 나눈` 나머지에 따라 값이 바뀌는 걸 함수로 만듭니다
def func(one,two):
    temp = (one-1)//2**(two)
    if temp%2 == 0:
        return '4'
    else:
        return '7'

for v in range(n+1):
    reversed_answer += func(a,v)

answer = reversed_answer[::-1]

print(answer)