[알고리즘] 백준 1065번 한수 (C)

devicii·2021년 8월 27일
1

c

목록 보기
3/6

문제

어떤 양의 정수 X의 각 자리가 등차수열을 이룬다면, 그 수를 한수라고 한다. 등차수열은 연속된 두 개의 수의 차이가 일정한 수열을 말한다. N이 주어졌을 때, 1보다 크거나 같고, N보다 작거나 같은 한수의 개수를 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 1,000보다 작거나 같은 자연수 N이 주어진다.

출력

첫째 줄에 1보다 크거나 같고, N보다 작거나 같은 한수의 개수를 출력한다.

예제 입력 1 예제 출력 1
110        1
예제 입력 2 예제 출력 2
1          1
예제 입력 3 예제 출력 3
210		   105
예제 입력 4 예제 출력 4
1000	   144

😕?!?!

처음 문제를 읽고 띠용 ? 하면서 문제부터 이해하기 어려웠다.
아래의 사진을 보고 한수라는 것이 무엇인지 이해했다.

1부터 99까지는 등차수열인지 비교할 수 없기에 모두 한수로 성립된다.
예를 들어 123의 경우 공차가 1인 등차수열이다. 그렇기에 한수가 성립된다.
112는 공차가 다르기에 한수로 성립될 수 없다.

Code


#include <stdio.h>

int hanFunc(int n);
int main(){
	int num, result;
	 printf("INSERT HERE...\n");
	scanf("%d", &num);

	result = hanFunc(num);
	printf("%d\n", result);
	return 0;
}

int hanFunc(int n){
	int count,hundred, teen, one;
	count = 0;
	if (n < 100)
		{
			return n;
		}
		else
		{
			for (int i = 100; i <=  n; i++)
			{
				hundred = i / 100;
				teen = (i % 100) / 10;
				one = (i % 100) % 10;
				if ((hundred - teen) == (teen - one))
				{
					count++;
				}
			}
			return (99 + count);
		}
}

풀이

  • 1000의 자릿수까지 한수를 찾아야 하니 (100의 자리 수 - 10의 자리 수) == (100의 자리 수 - 10의 자리 수) 가 된다면 한수이다.

  • 첫 번째 if에서 불필요한 연산을 없애기 위해서 n이 100보다 작다면 바로 return해준다. 1~99까지는 모두 한수이기 때문이다.

  • 100보다 n이 크다면 for문을 활용해 계산하는데 i를 100으로 둔다. 100부터 n의 수만큼 for를 돌리기 위해서다.

  • 100의 자릿수는 i / 100을 해서 구하고, teen은 (i % 100) / 10을 하면 구할 수 있다.
    예를 들어 i가 123이면 123 % 100 = 23. 23 / 10 = 2. 이렇게 구할 수 있고 일의 자리는
    (i % 100 ) % 10을 한다면 구할 수 있다. 예를 들어 123 % 100 = 23. 23 % 10 = 3.

  • 그렇게 모든 자리 수를 구한 뒤 (hundred - teen) == (teen - one)이 성립된다면 한수이기에 카운팅 한다. 이후 for가 종료된 뒤 1 ~ 100까지의 한수인 99와 count를 더해서 return 해준다.

profile
Life is a long journey. But code Should be short :)

0개의 댓글