[백준 1790] 수 이어쓰기2

www.acmicpc.net/problem/1790

1790번: 수 이어 쓰기 2

이분탐색이라고 되어있는데 이분탐색보다는 수학적 접근이 더 쉬운 것 같다.

n까지 써있는 수열에서 k번째 수를 찾는 문제이다.

예시에선 n=20 k=23인데 직접 찾아보자

1. 1~9까지 숫자(한 자리수) = 총 9개

23 -= 9

k = 14가 된다.

 

2. 10 ~ 99까지의 숫자(두자리수) = 총 90개(100-10)

14 < 90이다.

따라서 k는 두자리수 어딘가에 위치한 다는 의미이다.

 

14는 두자리수이므로 /2하면 7이 나온다. 23은 한자리수 9개 + 두 자리수 7개라는 의미이다.

9 + 7 = 16

1이나 6이라는 의미이다. 하지만 직관적으로 1이 13번째, 6이 14번째임을 알 수 있다.

 

일반화하자면

한자리수, 두자리수, 세자리수,,, n-1자리수 전체까지 포함하는지 확인하고

k가 n자리수 어딘가에 해당한다면

자리수를 찾는다.

 

#include <stdio.h>
#include <string>

using namespace std;
int n;
long long k;

int main(void)
{
  scanf("%d%lld", &n, &k);

  long long tmp_len = 1, tmp_num = 9;
  long long check = 0;
  while (k > tmp_len * tmp_num)
  {
    k -= tmp_len * tmp_num;
    check += tmp_num;
    tmp_len++;
    tmp_num *= 10;
  }

  int digit = (int)((k - 1) % tmp_len);

  long long res = check + 1 + (k - 1) / tmp_len;

  string tmp = to_string(res);
  if (res > n)
  {
    printf("-1\n");
  }
  else
  {
    printf("%c\n", tmp[digit]);
  }
  return 0;
}