백준 한수의 개수 구하기 (백준 1065 자바)

한수는 수학적으로 통용되는 개념은 아니다.

이 문제는 자리수가 각자 등차수열을 이루는 수의 개수를 구하는 문제로 보면 된다. 

예를 들어, 1234는 양의 정수이며 수열 1 2 3 4 는 등차수열이므로 1234는 한수이다.

100의 자릿수로 분리하면 1 0 0 인데 이는 등차수열이 아니므로 100은 한수가 아니다. 

이를 알고리즘으로 구현하려면 어떻게 해야 할까?

 

1) 한 자리 숫자는 한수로 정의한다. 수열은 '규칙이 있는 숫자의 나열'인데, 한 자리 숫자라고 해서 이 정의에 위배되지는 않는다. 어차피 한수는 통용되는 개념이 아니므로 이 문제에서 그렇게 정의한다고 보면 된다. 

2) 두 자리 숫자는 모두 공차가 정해진 등차수열이므로 한수이다.

3) 세 자리 숫자부터는 공차를 계산해 등차수열인지 확인해야 한다.

 

이 문제에서는 입력값을 1000 이하의 숫자로 제한하고 있고, 1000은 한수가 아니므로 세 자리 숫자의 등차수열 확인법만 구현해주면 된다.

등차수열은 이전 숫자와 다음 숫자의 차가 모두 같기 때문에, 나란히 놓여있는 세 수는 다음과 같이 표현할 수 있다.

a-d, a, a+d

여기서 가운데 숫자인 a에 2를 곱하면 그 직전과 직후 숫자의 합(2a)이 되는 것이 등차수열의 특징이다. 이 트릭을 이용해 세 자리 수가 등차수열임을 확인하는 han이라는 메소드를 정의하였다. 메소드 안에서는 숫자를 백의 자리, 십의 자리, 1의 자리로 분리하여 각각 변수 hun, ten, one에 저장한 뒤, 위 특징을 활용해 한수임을 확인하고 한수일 경우 1을, 한수가 아닐 경우 0을 리턴한다. 따라서 추가적인 확인 없이 리턴값을 결과값에 더하면 한수의 개수를 추가시킬 수 있다.

 

import java.util.*;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		int num = sc.nextInt();
		
		if (num<100){
			System.out.println(num);
		}
		else{
			int result = 99;

	  		for (int i = 111; i <= num; i++)
  				result += han(i);
			
			System.out.println(result);
		}
	}
	
	private static int han (int inum) {
		int hun = inum / 100;
		int ten = inum % 100 / 10;
		int one = inum % 10;
		
		if (ten*2 == hun + one) {
			return 1;
		}
        
		return 0;
	}
}

 

만약 입력된 수가 100 미만인 경우는 그 이하의 모든 수가 한수이므로 그대로 숫자를 출력하면 된다.

100을 넘어가는 경우 우선 결과값을 99로 초기화시키고, 100부터 하나씩 한수 확인 메소드를 돌려가며 한수일 경우 결과값을 1씩 늘려준다.

100~110까지는 한수가 될 수 없으므로 111부터 알고리즘을 적용하였다.