티바이트

출처 

Koreatech Online Judge(링크)


문제이해 

양의 정수를 1부터 일렬로 나열했을 때 (ex 123456789101112...) P번째에 오는 숫자를 구하는 문제이다.


문제접근 

자리수가 1개인 수(1~9), 2개인 수(10~99), 3개인 수(100~999), ... 를 구분하여 계산한다


구현 

아래와 같은 규칙이 있다.

- 자리수가 1개인 수를 모두 썼을 때는 길이가 9인 문자열이 생성된다.

- 자리수가 2개인 수를 모두 썼을 때는 길이가 90*2 = 180 인 문자열이 생성된다.

- 자리수가 3개인 수를 모두 썼을 때는 길이가 900*3 = 2700인 문자열이 생성된다.

만약 P 값으로 2889가 입력된다면, 그 수는 9+180+2700 이므로 세 자리 숫자 중 가장 마지막에 오는 숫자(999)일 것이다.


같은 방법으로, 임의의 P가 있을 때 이 수가 몇 자리 수로 이루어진 정수까지 썼을 때 나온 길이인지 계산할 수 있으며, 해당 자리 수를 가진 수 중 가장 작은 수까지 썼을 때 문자열의 길이도 구할 수 있다.


1부터 n까지 수를 일렬로 나열했을 때 문자열의 길이를 f(n)이라 한다면,

예를 들어, f(1000)과 f(10000)을 미리 계산할 수 있으므로, P가 이 사이의 값이라면 P는 네 자리 수까지 썼을 때의 값이다. 이 P값에서 f(1000)을 뺀 후 4로 나누고, 1000을 더하면, n값을 알 수 있는 것이다.  


실행결과 


코드
https://github.com/tibyte/algorithm-problems/blob/master/koreatech/1068/1068.cpp


 


  1. 행복을 찾아가야 행복도 다가옵니다.행복을 찾아가야 행복도 다가옵니다.행복을 찾아가야 행복도 다가옵니다.

  2. 행복을 찾아가야 행복도 다가옵니다!!행복을 찾아가야 행복도 다가옵니다!!행복을 찾아가야 행복도 다가옵니다!!!s

  3. 행복을 찾아가야 행복도 다가옵니다행복을 찾아가야 행복도 다가옵니다...행복을 찾아가야 행복도 다가옵니다...

댓글을 다는 공간입니다. (로그인하지 않아도 댓글을 남길 수 있습니다.)



게시판 목록은 좌측상단에 있습니다.

Statistics Graph