[JAVA] 백준 1065번 : 한수

1. 문제

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

 

--- More Details ---

등차수열이란?

연속하는 두 항의 차이가 모두 일정한 수열

식으로 나타내면 다음과 같다.

한수란?

각 자리수들이 등차수열을 이루는 수

 

한수의 예를 들어보면, 

123(공차 1) , 2468(공차 2) , 951(공차 -4), 등등이 있다. 

세자리 수 이상인 수는 이렇게 쉽게 한수를 생각해 낼 수 있는데, 한자리수와 두자리수는 한수를 어떻게 구할까?

한자리수와 두자리수는 모두 한수이다.

한자리수인 경우,(1,2,3,4...9) 따로 비교할 숫자가 없기 때문에 그 자체로 한수라 한다. 뭐 그래도 한수인 이유를 굳이 살펴보자면,  01(공차1) 02(공차2)... 09(공차9) 라고 볼수 있다. 
두자리수인 경우, 십의자리와 일의자리의 차가 공차가 되면서 한수라 할 수 있다. 10(공차 -1) 48(공차 4) 92(공차 -7)...  

따라서 모든 한자리수와 두자리수는 한수이다. 이점에 유의하며 문제를 풀어야 한다

 

추가로 11, 22, 99, 333, 이 수들은 한수일까?맞다. 공차가 0인 한수들이다.

 

2. 알고리즘 및 풀이

나는 함수를 main, getDigits, arithmetic_sequence함수 이렇게 세개 만들었다.

main은 말 그대로 main함수

getDigits함수는 각 자릿수를 뽑아내는 함수로, int형 배열을 반환한다.

arithmetic_sequence함수는 등차수열(arithmetic_sequence)인지 아닌지를 판별하는 함수이다.

 

getDigits함수 (각 자릿수 뽑아내어 배열로 저장하기)

public static int[] getDigits(int n){
		int[] digits= new int[3];
		for(int i=0;i<3;i++) {
			digits[i]=n%10;
			n=n/10;
		}
		
	    return digits;

	}

이제는 바로바로 짤 수 있어야 하는 함수중에 하나이다. 일단 문제에서 n은 1000이하의 수라 하였고, 우리가 100미만인 수(한자리수와 두자리수)는 따로 계산하고, 1000은 한수가 아니기 때문에 세자리수만 판정하면 된다. 따라서 각 자릿수를 얻는 것 또한 세자리 수만 계산할 것이기 때문에 digits배열은 크기가 3이면 된다.

일의자리부터 10을 나눈 나머지를 배열[0]에 저장하고, 10을 나누어 몫만 다시 n에 저장하고, ... 이렇게 반복하면된다.

246을 예로들어 표현하면

i=0일때, 246%10 = 6 이므로, digits[0]=6, n=(246/10=)24 

i=1일 때, 24%10 = 4 이므로, digits[1]=4, n=(24/10=)2 

i=2일때, 2%10=2 이므로 digits[2] = 2, n=(2/10=)0 

반복문 종료

그리고 getDigits함수는 digits배열을 반환한다. 

 

arithmetic_sequence 함수 (각 자리수가 등차수열인지 아닌지 판별하기)

한수(각 자릿수가 등차수열인 수)이면 cnt=1을 저장하여 반환한다.

1. 100미만의 수(한자리수, 두자리수)는 한수이므로 cnt=1이다.

2. n이 1000이라면 한수가 아니기때문에, cnt=0이다. 0이 아닌 다른수로 저장해도 상관없다.

3. 그 외(세자리수) getDigits함수를 통해 각 자릿수를 저장한 배열을 불러와 등차수열인지 아닌지 판별한다.

등차수열을 판별하는 방법은 (세자리수-두자리수) 와 (두자리수-한자리수)가 같으면 된다. 거꾸로 (한자리수 - 두자리수) 와 (두자리수 - 세자리수)가 같으면 된다. 즉, 연속된 수의 공차가 같으면 된다. 공차가 동일하면 cnt=1이다. 

public static int arithmetic_sequence(int n) {
		
		int cnt=0;
		if(n<100) cnt=1;
		else if(n==1000)	cnt=0;
		else {
			int[] digits = getDigits(n);
			if(digits[2]-digits[1]==digits[1]-digits[0])	cnt=1;
		}
		return cnt;
		
	}

 

main함수

int n = sc.nextInt();
int result=0;	//result: 한수의 개수를 저장
for(int i=1;i<=n;i++) {
	if(arithmetic_sequence(i)==1) result++;
}
System.out.println(result);

n에 숫자를 입력 받아 저장하고 1부터 n까지 반복문을 돌려 cnt의 개수, 즉 한수의 개수를 세어주면 된다. arithmetic_sequence함수를 불러 그 함수가 반환하는 값이 1이면 한수이므로 result를 1 증가 시키면 된다.

 

 

3. 전체 코드

import java.util.Scanner;
public class Main {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int result=0;
		for(int i=1;i<=n;i++) {
			if(arithmetic_sequence(i)==1) result++;
		}
		System.out.println(result);
		sc.close();
		
	}
	
	public static int[] getDigits(int n){
		int[] digits= new int[3];
		for(int i=0;i<3;i++) {
			digits[i]=n%10;
			n=n/10;
		}
		
	    return digits;

	}
	
	public static int arithmetic_sequence(int n) {
		
		int cnt=0;
		if(n<100) cnt=1;
		else if(n==1000)	cnt=0;
		else {
			int[] digits = getDigits(n);
			if(digits[2]-digits[1]==digits[1]-digits[0])	cnt=1;
		}
		return cnt;
		
	}
}

 

4. 링크

www.acmicpc.net/problem/1065

1065번: 한수