본문 바로가기

별걸다하는 IT/알고리즘 문제풀이

[백준 알고리즘 Baekjoon]1065번 한수 문제 풀이 및 설명, 알고리즘 여러가지 방법으로 풀기

[baekjoon algorithm]

단계 분류: 함수

알고리즘 분류: 브루트포스, 완전 탐색

[1065번] 한수

 

문제

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

 

입출력

입력: 첫째 줄이 1000보다 작거나 같은 자연수 N이 주어진다.

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

 

예제 입력

예제 출력

110

99

1

1

210

105

1000

144

↓ 문제 풀이는 아래로! ↓

풀어보지 않은 사람은 다 같이 풀어봐요~~!!

 

ANSWER

일단 한수가 뭔지 이해를 해야겠죠? 음 문제를 읽으니 좀 생각을 해야 이해할 수 있을 것 같은..

한수를 설명하는 단어는 결국 '어떤 양의 정수 X의 자리수가 등차수열을 이룬다면, 그 수를 한수라고 한다.' 이 한 줄이네요.

 

첫 번째 예시를 보니 각 자리가 등차수열을 이루는지 물어보는 것 같은 느낌인데 한 번 생각이 맞나 확인해봅시다.

110 인데 99개가 나왔다는 것은,

1~9까지는 한 자리수밖에 없으니까 다 한수에 들어갈 것 같고

10~99 또한 두 자리수라 각 자리수의 차이가 공차가 될 것 같아 한 수에 해당되나 보군요.

100 101 102 103 .... 110이 다 한수가 아니라는건데 음 ...

공차가 1이라면 123 이 한수, 공차가 0이라면 111이 한수, 근데 범위가 110까지이므로 둘 다 포함이 안되네요

즉 99개가 맞습니다!!

예! 바로 한수가 나오네요!!

근데 한수가 진짜 있는 수인가 문득 궁금.. (서칭해본결과 없는 것 같네요! ㅎㅎ 아마 문제를 위해서 임의로 명칭을 정의한 것 같아요)

 

해결방법은 자연수를 받아서 그 수가 한수인지 판별하는 함수를 정의할 수 있겠고

자연수를 받으면 그 자연수보다 작거나 같은 수들 중 한수가 몇개인지 리턴해주는 함수,

일단 두 가지가 생각나네요.

 

맨날 C++이 익숙하다보니 습관적으로 C++로 시작하는 것 같아서 JAVA를 먼저 볼게요. 첫 번째 풀이는 매 수를 한수인지 확인하는 방법으로 가볼게요. 고려려면 일단 각 수들이 등차수열인지 확인 하는 함수가 있어야겠죠? 그래서 등차수열이 맞을 때마다 한수개수를 하나씩 올려줄거예요.

 

[1065번 Java , 등차수열 함수, 공식 이용하기]

public static boolean IsArithmeticSeq(int[] arr, int lastIndex) {
      	int a = arr[0]; //첫째항
    	int d = arr[1]-arr[0]; //공차
    	for(int i=2;i<= lastIndex ;i++) { //다음 항부터 끝까지
    		if(arr[i]!=a+i*d)
    			return false;
    	}
    	return true;
}

중학교 때 배웠던 등차수열의 공식! 기억나나요?

n번째 숫자 = a+(n-1)d 이었죠?! 이 공식을 이용한 풀이예요. 다만 주의할점은 n은 번째를 의미한다는 것!! 

숫자가 1,2,3...이렇게 간다고 하면 배열은 0,1,2,..이렇게 간다는 걸 주의해줘야합니다.

 

예를 들어 1234숫자의 경우 arr[0]=1, arr[1] = 2, arr[2]=3, arr[3]=4가 됩니다.

arr[3]은 어떻게 구하느냐 arr[0]+(4-1)(arr[1]-arr[0]) = 4 이렇게 구할 수 있겠죠?

즉 공식은 arr[i] = arr[0] + i*d 가 됩니다.

 

[1065번 Java , 등차수열 함수, 각 항 공차 비교]

이렇게 공식을 이용할 수도 있겠지만, 각 항 사이의 공차가 일정한지 판별하는 방법도 가능하겠죠?

 public static boolean IsArithmeticSeq(int[] arr, int size) {
    	int d = arr[1]-arr[0]; //공차
    	for(int i=2; i<size; i++) {
    		if(arr[i]-arr[i-1] != d)
    			return false;
    	}
    	return true;
}

차이점을 조금 주기 위해(?) 이 함수는 매개변수를 마지막 인덱스가 아닌 배열 전체 크기로 받아봤어요 ㅎㅎ

 

[1065번 Java]

이제 메인함수를 구성해볼까요?

일단 99까지는 모두 한수이기 때문에 굳이 시간을 소비해가면서 판별할 필요가 없죠 ㅎㅎ

int count = 99;
if(N<100) {
    System.out.println(N);
    return;
}

N이 33일 때는 한수의 개수가 33개인것처럼, 100보다 작은 두 자리 숫자가 입력되면 그 숫자 그대로를 출력해주고 종료해줍시다. 100이상인 N의 의 경우, 한수는 기본적으로 99개를 갖고 시작할거예요.

 

JAVA - 전체코드

[1065번 Java- 수마다 한수인지 판별하기]

N이 들어오면 100부터 N까지 차례대로 한수인지 아닌지 판별해주는 식으로 코드를 짜봤어요 ㅎㅎ

import java.util.Scanner;
public class Main{	
    public static int count;
	public static void main(String[] args) {
    	Scanner sc = new Scanner(System.in);
    	int N = sc.nextInt();
    	
    	if(N<100) {
    		System.out.println(N);
    	}else{
            count = 99;
        	for(int i=100; i<=N; i++) {
    		    if(IsHanNumber(i)) {
    		    	count++;
    		}			
    	}
    	System.out.println(count);
        }
    }
    public static boolean IsHanNumber(int num) {
    	if(num == 1000) return false; //어차피 1000은 한수가 아님
    	int[] placeValue = new int[3]; //최대 3자리 수
    	for(int i=0;i<3;i++) {
    		placeValue[i] = num%10;
    		num /=10;
    		if(num == 0)
    			break;
    	}
    	return IsArithmeticSeq(placeValue, 3);
    }
  public static boolean IsArithmeticSeq(int[] arr, int size) {
    	int d = arr[1]-arr[0];
    	for(int i=2; i<size; i++) {
    		if(arr[i]-arr[i-1] != d)
    			return false;
    	}
    	return true;
     }
}

4자리 숫자는 1000밖에 없는데 굳이 얘 하나 때문에 4자리까지 생각해주기보단, 1000이 한수면 1을 더하고 아니면 무시하는 방식으로 처리하는 게 쉽겠죠?

 

 

[1065번 Java- 범위 내 가능한 한수 개수 반환 방법]

이번에는 다른 방법으로 풀어봅시다. 매 수에 확인과정을 거치는 방안이 아닌, 범위에 있는 한수를 계산해서 총 계수를 반환하는 코드입니다.

 

JAVA - 전체코드

import java.util.Scanner;
public class Main{	
	public static int count;
	public static void main(String[] args) {
    	Scanner sc = new Scanner(System.in);
    	int N = sc.nextInt();
    	
    	if(N<100) {
    		count = N;
    		System.out.println(count);
    		return;
    	}
    	count = 99;
    	if (N == 1000) N = 999;
    	HowManyHanNumber(N);
    	System.out.println(count);
    } 
	public static void HowManyHanNumber(int n) { 
		int first = n/100, second = (n%100)/10, third =n%10;
		int tens, units;
		for(int a=1; a<=first; a++) {
			for(int d = -a/2;d<(float)(10-a)/2;d++) {
				tens = a+d; units=tens+d;
				if(a==first) {
					if((tens*10+units)>second*10+third) {
						continue;
					}
				}
				count++;
			}
		}
	}    
}

메모리: 14292KB

시간: 100ms

코드길이: 769B

아마 추가적으로 설명이 필요할 부문은 범위 정도 일 것 같은데요

백의 자리가 a로 시작하는 세자리 수가 있다고 하면 각 자리수는 등차수열 특징에 의해 a, a+d, a+2d 이렇게 됩니다! 즉 마지막 최소(공차가 마이나스일때)나 최대값(공차가 플러스일 때)을 갖는 마지막 일의자리를 기준으로 범위를 계산했어요 ㅎㅎ a+2d는 당근 0보다 크거나 같아야겠죠? a+2d>=0 을 d를 기준으로 정리하면 d>-(a/2)가 됩니다. 맥스도 a+2d<10을 정리해서 잡아줬어요. 

 

 

[1065번 C++]

이번에는 C++로 풀어볼게요. 위의 풀이는 뒤에서부터 차곡차곡 배열로 옮겨담았는데요

즉 123이면 배열에 담기는 순서는 {3,2,1} ( 공차의 부호가 반대가 되긴 하지만 어차피 등차수열인지만 판별하면 되니까 !)

이번에는 좀 다르게 123이면 {1,2,3}이렇게 넣어줄게요.

 

[자연수 vector로 변환하기 C++]

vector<int> getVector(int N, int leng) {
	vector<int> placeValue;
	int place;
	while (leng != 0) {
		place = pow(10, leng - 1);
		placeValue.push_back(N / place);
		N -= (N / place)*place;
		leng -= 1;
	}
	return placeValue;
}

순서대로 담기게 하기 위해서 pow함수를 써줬습니다 ㅎㅎ pow(a,b)하면 a^b 를 리턴해줍니다 

 

C++ - 전체코드

로직은 자바로 푼 거랑 똑같습니다.

#include<iostream>
#include<vector>
#include<math.h>
using namespace std;
bool IsHanNumber(vector<int> N);
vector<int> getVector(int, int);
int main() {
	int N; vector<int> n;
	cin >> N;
	if (N < 100) {
		cout << N;
		return 0;
	}
	if (N == 1000) N = 999;
	int count = 99;
	for (int i = 100; i <= N; i++) {
		n = getVector(i, 3);
		if(IsHanNumber(n)) count++;
	}
	cout << count;
	return 0;
}

vector<int> getVector(int N, int leng) {
	vector<int> placeValue;
	int place;
	while (leng != 0) {
		place = pow(10, leng - 1);
		placeValue.push_back(N / place);
		N -= (N / place)*place;
		leng -= 1;
	}
	return placeValue;
}
bool IsHanNumber(vector<int> N) {
	int size = N.size();
	int d = N[1] - N[0];
	for (int i = 2; i < size; i++) {
		if (N[i] - N[i - 1] != d)
			return false;
	}
	return true;
}

이렇게 푸신분들도 있네요 ㅎㅎ 가독성은 완전 낮지만 코드 길이는 가장 짧은 듯..?

 

 

도움이 되셨나요? ㅎㅎ

다음에는 다음 문제로 또 찾아뵐게요 ㅎㅎ 도움이 됐다면 공감!!

오늘도 찾아주셔서 감사합니다 :)