#include<stdio.h>
#include<vector>
using namespace std;
int main()
{
int n;
scanf("%d", &n);
int lt = 1;
int k = 1;
int rt, cur = 0;
int count = 0;
while(lt != 0)
{
lt = n / (k * 10);
cur = (n / k) % 10;
rt = n % k;
if(cur > 3)
{
count += (lt+1) * k;
}
else if(cur == 3)
{
count += (lt * k) + (rt + 1);
}
else
{
count += lt * k;
}
k *= 10;
}
printf("%d", count);
return 0;
}1. 포인터를 활용하여 풀면 아주 쉽게 풀 수 있는 문제이다.
포인터는 rt, lt, cur 총 3개를 활용한다. 포인터의 이동은 k를 활용한다.
5367을 예로 들겠다.
시작은 1의 자리 숫자인 7부터 시작한다.
lt는 cur의 왼쪽인 536을 가리키고, rt는 cur의 오른쪽인 0을 가리킨다.
cur ↓
| 5 | 3 | 6 | 7 |
여기서 중요한데, cur이 3보다 큰지, 같은지, 작은지에 따라서 count 개수가 달라진다.
위 상황처럼 cur > 3 일 경우를 보면 0007 ~ 5363까지 3이 등장한다.
이는 (lt + 1) * k = (536+1) * 1 = 537개 로 계산할 수 있다.
lt + 1인 이유는 0007, 즉 7일 때 lt가 0이기 때문에 0~536개인 537개이다. k는 현재 cur의 자리수이다.
전체 카운트가 끝나면 k에 10을 곱해서 cur의 자리수를 한 단계 올려준다.
cur ↓
| 5 | 3 | 6 | 7 |
위 두 상황을 보면 lt, cur, rt 를 계산할 수 있는 식을 도출할 수 있다.
lt = n / (k * 10) = 5367 / (10 * 10) = 5367 / 100 = 53
cur = (n / k) % 10 = (5367 / 10) % 10 = 536 % 10 = 6
rt = n % k = 5367 % 10 = 7
위 상황과 동일하게 cur > 3 이므로
(lt + 1) * k = (53+1) * 10 = 540개 로 계산할 수 있다.
cur ↓
| 5 | 3 | 6 | 7 |
cur = 3 이므로
0300 ~ 5367 까지 3이 등장한다.
3을 빼고 보면 000~567까지 등장한다는 의미이므로 568개이다.
(lt * k) + (rt+ 1) = (5 * 100) + (67 + 1) = 568개
cur ↓
| 5 | 3 | 6 | 7 |
cur > 3 이므로
(lt + 1) * k = (0+1) * 1000 = 1000개
이후로 lt != 0 조건에서 false로 while문이 break 된다.
총 개수 = 537 + 540 + 568 + 1000 = 2645개
