[★1][백준1065번]한수 (JAVA)

[★1][백준1065번]한수 (JAVA)

1065번 문제 ☞ https://www.acmicpc.net/problem/1065

난이도 ☞ [★1]

한수

• 문제
  • 어떤 양의 정수 X의 각 자리가 등차수열을 이룬다면, 그 수를 한수라고 한다. 등차수열은 연속된 두 개의 수의 차이가 일정한 수열을 말한다. N이 주어졌을 때, 1보다 크거나 같고, N보다 작거나 같은 한수의 개수를 출력하는 프로그램을 작성하시오.
  • 첫째 줄에 1,000보다 작거나 같은 자연수 N이 주어진다.

  • 첫째 줄에 1보다 크거나 같고, N보다 작거나 같은 한수의 개수를 출력한다.

    예제입력	예제출력
    110	99

    예제입력	예제출력
    1	1

    예제입력	예제출력
    210	105

    예제입력	예제출력
    1000	144

    예제입력	예제출력
    500	119

내가 푼 풀이

우선 들어가기에 앞서 등차수열(Arithmetic Sequence)이라 함은 연속하는 두 항의 차이가 같은 수를 말한다. 즉, [1, 3, 5, 7, 9]나 [1, 2, 3, 4, 5]처럼 차이가 일정한 수를 말한다. 이러한 등차수열 일반항을 식으로 나타내보면 아래와 같다.

x번째 항을 $a_x$공차를 d라고하면 등차수열의 일반항은 아래와 같으며,

$a_n$ = $a_1$ + (n - 1)d

x = 1을 대입하면 아래와 같다.

$a_n$ = $a_1$ + (n - 1)d

위의 식에서 d는 공차를 말하며, 공차는 연속하는 두 수의 차를 말한다 1~99까지는 모두 등차수열이며, 1~9까지는 하나하나 그 자체가 수열에 속한다. 예를 들면, 82는 -6인 수열이고, 28은 6인 수열이다. 그래서 이 문제에서 생각해야할 문제는 100보다 크냐 작냐에 따라 나누어 생각해보면 된다.

[ 풀이 1 ]

메모리 : 17712KB
시간 : 220ms

Scanner

import java.util.Scanner;

public class Main {

	// 함수 구현부
	public static int arithmetic_sequence(int num) {
		int cnt = 0;        // 한수 갯수

		if (num < 100) {
			return num;
		} else {
			cnt = 99;

			for (int i = 100; i <= num; i++) {
				int hundred = i / 100;      // 백의 자리
				int ten = (i / 10) % 10;    // 십의 자리
				int one = i % 10;       // 일의 자리

				if ((hundred - ten) == (ten - one)) {       // 각 자리수가 수열을 이루면
					cnt++;      // 한수 갯수 증가
				}
			}
		}

		return cnt;
	}

	public static void main(String[] args) {
		
		Scanner s = new Scanner(System.in);

		System.out.print(arithmetic_sequence(s.nextInt()));
		s.close();

	}

}

쉽게 말하자면 100의 자리에서 10의 자리를 뺀 값이, 10의 자리에서 1의 자리의 뺀 값이 같으면 등차수열이다. 이 등차수열을 이루는 수가 한수이다. 이번 문제는 함수 구현부가 제일 중요한 문제이며, 알고리즘 이해를 해야하는 문제이다. 다음은 BufferedReader로 구현한 것이다. 함수 구현부는 따로 만지지 않아도 되며, main부분만 만져주면 된다.

[ 풀이 2 ]

메모리 : 14184KB
시간 : 124ms

BufferedReader

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
	// 함수
	public static int arithmetic_sequence(int num) {
		int cnt = 0; 		// 한수 갯수

		if (num < 100) {
			return num;
		} else {
			cnt = 99;

			for (int i = 100; i <= num; i++) {
				int hundred = i / 100; 		// 백의 자리
				int ten = (i / 10) % 10; 		// 십의 자리
				int one = i % 10; 		// 일의 자리

				if ((hundred - ten) == (ten - one)) { 		// 각 자리수가 수열을 이루면
					cnt++; 		// 한수 갯수 증가
				}
			}
		}

		return cnt;
	}

	public static void main(String[] args) throws IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		System.out.println(arithmetic_sequence(Integer.parseInt(br.readLine())));

	}

}

이번 문제는 매우 쉬운 문제(?)라면 쉬운 문제였다고 생각이 된다.

BKJN 카테고리 내 다른 글 보러가기