1598 꼬리를 무는 숫자 나열

1598 꼬리를 무는 숫자 나열

[Baekjoon] 1598 꼬리를 무는 숫자 나열, 문제 풀이.
프로그래밍 언어: C

문제

1598 꼬리를 무는 숫자 나열

접근

처음에는 규칙을 찾아보려고 했다.
두 개의 숫자 a와 b가 주어질 때, a와 b를 4로 나누고 몫의 차이, 나머지의 차이를 구한 다음 두 차이를 더하면 직선거리를 구할 수 있다고 생각했다. 하지만 되는 경우도 있었고 안되는 경우도 있었다. 예를 들어 a가 4, b가 5라면 직선 거리는 4칸이다. 하지만 이 계산식에 의하면 1칸이 차이라고 나온다. 반면, a가 1, b가 11이라면 직선 거리는 4칸, 이 계산식에 의해서도 4칸이 나온다. 즉, 일반화가 되지 않는다.
왜 이런 오류가 발생하는지 생각해보니 이 수열에서 처음에 나오는 숫자는 1이다. 위의 계산식은 좌표계를 이용하는 식이기 때문에 좌표의 원점을 0으로 설정할 필요가 있었다. 즉, a와 b 모두 -1을 함으로서 좌표계를 수정해주어야 한다.

	a = a - 1; b = b - 1; // 원점을 0으로 만들기 위해서 모든 숫자에 -1을 해준다.

또한, a와 b 둘 중 무엇이 크다고 정의해주기 않았기 때문에 차이를 구할 때, 음수가 나올 수 있다. 따라서 abs() 함수를 이용하여 절대값을 취해준다. abs() 함수는 stdlib.h를 헤더파일로 가지기 때문에 선행 처리문에 표시 했다.

#include <stdlib.h> // abs 함수를 사용하기 위한 헤더파일
...
	result = abs(a / 4 - b / 4) + abs(a % 4 - b % 4); // 4로 나눈 몫끼리 빼고, 4로 나눈 나머지끼리 빼서 더한다. (절대값)
...

전체 코드

#include <stdio.h>
#include <stdlib.h> // abs 함수를 사용하기 위한 헤더파일

int main(void)
{
	int a, b;
	int result = 0;

	scanf("%d %d", &a, &b);

	a = a - 1; b = b - 1; // 원점을 0으로 만들기 위해서 모든 숫자에 -1을 해준다.
	result = abs(a / 4 - b / 4) + abs(a % 4 - b % 4); // 4로 나눈 몫끼리 빼고, 4로 나눈 나머지끼리 빼서 더한다. (절대값)
	printf("%d", result);
}

개선 및 부족한 사항

• 좌표계를 이용한 계산을 할 때에는 원점이 0인지 확인하자.
• abs()와 관련된 사항을 정리하자.