[백준 알고리즘] 1065번 - 한수

1. 문제, 예시 실행결과

 

 함수 카테고리의 마지막 문제이다. 문제를 요약하자면, 등차수열과 관련된 문제이다. 등차수열은 이미 고등학교시절 배운 내용이고, 잘 알려진 일반항도 존재하기에, 내가 한 일은 첫항과, 공차를 구하는 것이었고 이를 함수로 구현한것 밖에 없다. 다음은 문제와 예시 실행결과이다.

 

출처: https://www.acmicpc.net/problem/1065

1065번: 한수

---

문제 1065번

---

 문제는 간단하다. 한수를 이해하는데 어려움이 있을 수 있다. 한수에 대해서는 문제 풀이 과정에서 더욱 자세히 설명할 것이다. 다음은 예시 실행결과이다.

---

예시 실행결과

---

 210이 입력되면, 1부터 210까지의 수 중에서 한수에 해당하는 수의 갯수를 출력하면 된다. 다음은 풀이 과정이다.

 

2. 문제 풀이

 

 이 문제를 풀기 위해선 '한수'에 대한 확실한 이해가 필요한 것 같다. 사실 그렇게 어렵지도 않다. 만약 123이란 숫자가 있다고 생각해보자. 그리고 이 수를 각 자리수별로 나눠 하나의 수열을 만든다. 표현하자면 다음과 같을 것이다,

---

123 ->  1, 2, 3

---

 위의 수열(1, 2, 3)은 첫째항이 1이고, 공차가 1인 수열이라고 할 수 있다. 즉 하나의 수를 자릿수별로 나누고, 이 자릿수별로 나눈 수열이 등차수열일때, 이 수를 한수라고 한다. 생각해보면 결국 1부터 99는 항이 한개이거나 항이 두개인 등차수열이다. 정리하자면 1부터 99에 해당하는 수는 무조건 한수라는 것이다. 결국 우리는 100부터 1000까지의 숫자가 한수인지 아닌지에 대해 판단해야한다. 내가 사용한 알고리즘은 다음과 같다.

---

1. 한수인지 아닌지 판별해야하는 수가 100이하면 무조건 한수로 판단.

2. 수가 100 이상이면 판별 알고리즘을 사용.

3. 판별 알고리즘은 해당 수의 첫째항과 공차를 구하고 등차수열의 일반식을 구현한 함수에 인수로 전달하여 값을 받아온다.

4. 이 값을 가지고 한수인지 아닌지를 판별한다.

---

 내가 알고리즘을 정리하는 실력이 뛰어나지 않아, 글만으로는 이해하기 힘들 것 같다. 다음은 내가 작성한 등차수열을 판별하는 함수인 aberration() 함수와 등차수열의 일반항을 코드로 구현한 함수인 recurrence() 함수이다.

int aberration(int num, int d) {
	int a = num / 100;
	num = num % 100;
	int a2 = num / 10;
	int a3 = num % 10;
	if (a2 == recurrence(a, 1, d) && a3 == recurrence(a, 2, d))
		return 1;
	else
		return 0;
}

int recurrence(int a, int i, int d) {
	return a + (i * d);
}

 이 두 함수를 사용하여, 한수인지 아닌지를 판별하고, 함수라면 count변수에 1을 더하는 방식으로 구현하였다. 결과적으로 우리는 해당범위에 있는 수중 한수의 갯수만을 출력하면 되기 때문이다. 다음은 전체 코드이다.

#include <stdio.h>

int aberration(int num, int d);
int recurrence(int a, int i, int d);
int main(void) {
	int input;
	int count = 0;
	scanf("%d", &input);

	for (int i = 1; i <= input; i++) {
		if (i < 100)
			count++;
		else{
			int n1 = i / 100;
			int n2 = (i % 100) / 10;
			if (aberration(i, n2 - n1))
				count++;
		}
	}
	printf("%d", count);
	return 0;
}

int aberration(int num, int d) {
	int a = num / 100;
	num = num % 100;
	int a2 = num / 10;
	int a3 = num % 10;
	if (a2 == recurrence(a, 1, d) && a3 == recurrence(a, 2, d))
		return 1;
	else
		return 0;
}

int recurrence(int a, int i, int d) {
	return a + (i * d);
}

 

3. 결어

 

 함수 카테고리를 마무리하였다. 아직 갈길이 멀지만 ㅠㅠ 다음엔 다음 카테고리를 올릴 것이다.