백준 1065번 - 한수

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

1065번: 한수

생각 :

이 문제는 1<= N <=1000인 N값이 주어졌을때, 1<= 한수 <=N의 개수를 구하는 것이다.

접근 방법 : 각 자리수마다 나올 수 있는 한수의 개수를 파악해야 한다. 길이가 1000으로 정해져 있다는 것에 주목하고, 한수의 본질을 파악한다면 비교적 쉽게 풀어낼 수 있다.

우선 한수의 뜻은 "각 자리수들이 등차수열을 이루는 수"이다. 등차수열이란 각 항들이 일정한 차이를 보이는 수열이다. 예를 들면 한수는 123(공차 1), 753(공차 -2), 111(공차 0)등이 가능하다.

그런데 여기서부터 헷갈리기 시작할 것이다. 3자리수 이상이면 쉽게 알 수 있는데 과연 3자리수 미만은 어떻게 될까?
결론부터 얘기하면 1자리수, 2자리수들은 모두 한수가 된다.

1자리수 인 경우 1,2,3...,9인데 이 수들은 따로 비교할 수들이 없어 한수로 그냥 인정을 해준다.
2자리수 인 경우 12,13,14,....,58,59,....97,98,99 등이 있는데 이 수들은 구할 수 있는 공차가 1개 밖에 없다.(10의자리 - 1의 자리) 따라서 공차가 뭐가 되었던 간 한수로 인정이 된다.

이게 사실 나도 풀면서 애매했는데 문제의 샘플 데이터로 110이 주어진 걸 보고 이해할 수 있었다. 110의 경우 3자리수일때 나올 수 있는 한수가 없기 때문에 2자리수까지 나온 한수가 전부이다. 따라서 샘플 데이터로 110일때 한수의 개수는 99였으므로 1자리, 2자리의 한수의 개수는 99개가 된다. 이를 식으로 나타내면 다음과 같다.

if (i < 100) han = i;

이제 나머지 한수들을 구해야 하는데 우선 필요한 작업은 각 자릿수들을 쪼개서 분리해줘야 한다는 것이다.

 

import java.util.Scanner;

public class 한수 {

	public static void main(String[] args) {

		Scanner sc = new Scanner(System.in);

		int N = sc.nextInt();
		int cnt = 0;

		if (N < 100) {
			System.out.println(N);
			return;
		} 
		else {
			cnt = 99;
			for (int i = 100; i <= N; i++) {
				int a = i / 100;
				int b = (i / 10) % 10;
				int c = i % 10;
				if(a-b == b-c)
					cnt++;
			}
			
			System.out.println(cnt);
		}
	}

}