BOJ 1065 - 한수

문제

BOJ 1065 - 한수

어떤 양의 정수 X의 각 자리가 등차수열을 이루면 X를 한수라고 한다. 예를 들어 1, 7, 12, 321, 246은 한수이고, 100, 2위, 421은 한수가 아니다. 1부터 N까지의 자연수 중 한수의 개수를 구하는 문제다.

입력

• 첫째 줄: 자연수 N (1 ≤ N ≤ 1,000)

출력

1부터 N까지 한수의 개수

예제

풀이

1~99 사이의 수는 모두 한수임을 이용한 최적화를 적용한다. 100 이상의 수에 대해서는 백의 자리, 십의 자리, 일의 자리를 분리하여 등차 조건을 검사한다.

1. N이 99 이하이면 N 자체가 한수의 개수다 (1자리, 2자리 수는 모두 한수).
2. N이 1000이면 N을 999로 조정한다 (1000은 한수가 아님).
3. 100 이상의 수에 대해 각 자리수를 추출하고, (백의 자리 - 십의 자리) == (십의 자리 - 일의 자리) 조건으로 등차수열 여부를 판단한다.
4. 기본 한수 수(99개)에 100 이상에서 발견된 한수를 더해 반환한다.

핵심 아이디어: 199는 모두 한수이므로 초기값을 99로 설정하고, 100N 범위에서만 등차수열 조건을 검사하면 된다.

코드

package com.ssafy.an.day049;
 
import java.util.Scanner;
 
public class Day36BOJ1065한수갯수함수만들기 { // 1065 한수
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		System.out.println(cal(sc.nextInt()));
		sc.close();
	}
 
	private static int cal(int n) {
		int cnt = 99;
		if (n < 100)
			return n;
		else {
			if (n == 1000)
				n = 999;
			for (int i = 100; i <= n; i++) {
				int h = i / 100;
				int t = (i / 10) % 10;
				int o = i % 10;
				if ((h - t) == (t - o))
					cnt++;
			}
		}
		return cnt;
	}
}

복잡도

• 시간: O(N) — 100~N 범위를 순회
• 공간: O(1) — 카운터 변수 외 추가 자료구조 없음