알고리즘/Baekjoon
백준 1065: 한수 (C++)
개발하는 크롱
2020. 11. 19. 15:20
반응형
문제 링크: www.acmicpc.net/problem/1065
문제 설명:
어떤 양의 정수 X의 각 자리가 등차수열을 이룬다면, 그 수를 한수라고 한다. 등차수열은 연속된 두 개의 수의 차이가 일정한 수열을 말한다. N이 주어졌을 때, 1보다 크거나 같고, N보다 작거나 같은 한수의 개수를 출력하는 프로그램을 작성하시오.
문제 접근 방법:
N은 1000이하의 자연수이므로 init()함수를 통해 1~1000까지 한수인지 아닌지를 배열 hansoo에 저장해뒀다.
hansoo[i] : i가 한수이면 1, 아니면 0
한 자리 혹은 두 자리 숫자면 무조건 연속된 두 개의 수의 차이가 일정하므로 한수이다.
세 자리 이상 숫자인 경우 백의 자리, 십의 자리, 일의 자리 각 숫자를 구해서 차가 일정한지 확인하고 한수인지 아닌지를 구분했다.
이후 N을 입력 받으면 hansoo배열을 인덱스 1~N을 돌면서 한수 개수를 세서 출력했다.
#include <cstdio>
//무식하게 풀기 : 1000이하의 한수 모두 찾아 배열에 표시
int hansoo[1001]; //1을 배열 인덱스 1에
//한수 배열 만들기 : 한수면 1, 아니면 0
void init() {
hansoo[0] = 0;
for (int i = 1; i < 100; i++) {
hansoo[i] = 1; //100이하의 자연수는 모두 한수
}
for (int i = 100; i < 1001; i++) {
int a = i / 100;
int b =i / 10 - a * 10;
int c = i % 10;
if ((a - b) == (b - c)) {
hansoo[i] = 1;
}
else hansoo[i] = 0;
}
}
int main() {
int input = 0, output=0;
scanf("%d", &input);
init();
for (int i = 0; i < input + 1; i++) {
if (hansoo[i] == 1)
output++;
}
printf("%d", output);
}
반응형