C언어 - 백준 알고리즘 1065번 (한수)

실버 4 등급의 문제이다.

이 문제는 문제를 이해하는 것이 아주 중요하다. 한수의 정의를 이해하는 것이 정말 어려웠다.

정수를 각 자리수로 분리해서 등차수열을 이루는 수가 한수이다. 예를 들어 134는 1 , 3,  4로 분리할 수 있는데 등차수열이 아닌 정수이다. 그러므로 134는 한수가 아니다.

135는 1, 3, 5로 분리할 수 있는데 공차가 2인 등차수열을 이루므로 한수라고 할 수 있다.

이 문제에서는 1000까지 정수로 한수의 개수를 구하는 문제인데 0~99까지는 공차가 1인 등차수열을 만족한다.

그래서 세자리의 정수만 고려하면 된다.

나는 처음에 문제를 접근하는 것이 너무 어려워서 저렇게 표를 만들어서 규칙을 찾으려고 정말 고생을 했는데 접근 방법이 잘못되었다. 

#include <stdio.h>

int hansoo(int num) {

	int a, b, c;
	

	if (num < 100)

		printf("%d", num);

	else
	{
		int cnt = 99;

		for (int i = 100; i <= num; i++) {


			a = i / 100;
			b = (i % 100) / 10;
			c = (i % 100) % 10;

			if ((c - b) == (b - a))
				cnt++;
		}
		printf("%d", cnt);

	}
		
}
int main(void) {

	
	int num;
	scanf("%d", &num);
	hansoo(num);
}

1. 세자리의 정수인지 판별을 먼저하고

2. 자릿수를 분리한다.

3. 반복문으로 등차수열을 이루는지 확인하고, 등차수열을 이룰 때 마다 카운트

 

여기서 등차수열을 이루는지 확인하려면 분리한 자릿수(등차수열의 각 항)의 차가 똑같으면 된다.

즉, 공차수열의 공차 d가 각 항마다 일치하는지 체크하라는 말이다.

 

공차를 사용해서 문제를 해결해야 한다는 것은 알고 있었는데 어려웠다.

 

<오늘의 느낀점>

알고리즘 문제 풀 때 요구조건을 순서대로 적는 것이 좋다고 느꼈다.

리처드 파인만이 양자역학 문제를 풀 때 썼던 알고리즘이

1. 문제를 칠판에 적는다.

2. 골똘히 생각한다.

3. 답을 칠판에 적는다.

라고 한다. 우스갯소리처럼 들리겠지만 우선적으로 해야 할 일을 적는 것이 문제 풀이에 도움이 된다는 뜻인 것 같다.