https://www.acmicpc.net/problem/1065
문제
> 어떤 양의 정수 X의 각 자리가 등차수열을 이룬다면, 그 수를 한수라고 한다.
> 등차수열은 연속된 수들이 일정한 차이를 가지는 수열이다.
> N이 주어졌을 때, 1보다 크거나 같고, N보다 작거나 같은 한수의 개수를 출력하라.접근
1부터 99까지는 한수이므로 N이 100이상일때부터만 생각하면 된다.
100이상의 N이 들어오면 한수를 판별하는 함수에서 자릿수로 쪼개 각각의 차이를 구해 서로 비교한다.
모두 비교한 값이 같다면 누적하고 아니면 다음 수로 넘어간다. 누적된 한수의 개수를 출력한다.
문제해결
> 한수 판별 함수를 정의한다. 수가 들어오면 해당 수를 100보다 크거나 같을 때까지 반복한다.(99까진 한수이므로)
> 수의 자릿수를 구하는 연산을 하고 각 자릿수를 벡터에 저장한다. 기준으로 0번인덱스와 1번인덱스의 차이를 가져온다. 최소세자리 숫자이고, pushback으로 0부터 채워지므로 예외는 없다.
> 가져온 0과1번의 차이와, 1번부터 마지막 자릿수까지의 연속된 수의 차이를 비교한다. 다른 차이가 존재한다면 다음 수로 넘어간다. 만약 차이가 다 같다면 cnt를 누적한다.
> N을 입력받고 99이하인지 확인하고 99이하면 N을 출력하고, 이상이면 hansu연산을 한 뒤 99를 더해주고 출력한다.코드
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
vector<int> num;
int hansu(int i)
{
int cnt = 0;
while (i >= 100)
{
int tmp = i;
bool valid = false;
num.clear();
while (tmp > 0)
{
num.push_back(tmp % 10);
tmp /= 10;
}
int diff = num[0] - num[1];
for (int j = 1; j < num.size() - 1; j++)
{
if (num[j] - num[j + 1] != diff)
{
valid = true;
break;
}
}
if (!valid) cnt++;
i--;
}
return cnt;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int N;
cin >> N;
if (N <= 99)
{
cout << N << '\n';
return 0;
}
cout << hansu(N) + 99 << '\n';
}
후기
막상 하고나니 최대 1000까지였다. 1000은 한수가 아니므로 999까지 보면된다. 따라서 굳이 벡터를 안쓰고 변수 세개로 각 자릿수를 담아 계산하면 된다. 그래도 1000이상일때를 생각해서 미리 연습했다고 생각하자.
