[백준] 1065번 - Java(자바)

백준 1065번 자바

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

1065번: 한수

 

문제 내용은 아래 더보기를 누르면 된다.

 

 

 

알고리즘

양의 정수 X의 각 자리가 등차수열을 이루는데, 그 수를 한수라고 한다.

등차수열은 연속된 두 개의 수의 차이가 일정한 수열을 말한다.

N이 주어지면, 1 <= 한수 <= N 의 조건을 만족하는 한수의 개수를 출력한다.

N은 1000보다 작거나 같은 자연수이다.

 

등차수열이 조금 헷갈린다면 아래 더보기를 누르면 된다.

등차수열이란?

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

예를들면, [1, 3, 5, 7, 9 ...]은 등차수열이다.

이때 두 항의 차이는 이 수열의 모든 연속하는 두 항들에 대해 공통적으로 나타나는 차이므로, 공차라고 한다.

즉, 이 수열의 공차는 2이다.

 

수열의 일반항은 다음과 같다.

 

이제 우리가 알아야할건 주어지는 N은 1000개 이하라는 것이다.

그리고 1~ N 사이의 값들이 한수인지 아닌지 카운트를 세주면 된다.

 

1 ~ 9 는 자릿수 1개

10 ~ 99 는 자릿수 2개

100 ~ 999는 자릿수 3개

1000는 자릿수 4개

 

즉, 우리가 검사해야하는 부분은 100 ~ 999 와 1000이다.

왜 그런지 모르겠다면 아래 그림을 살펴보자.

문제의 예제 및 출력을 보면 1~99는 전부 한수라고 되어있다.

위 그림을 살펴봐도 1 ~ 9 는 길이가 1개인 등차수열이다.

10 ~ 99 또한 각 자리수를 뺀 값이 공차인 등차수열이다.

그래서 우리가 검사해야할 수는 100 ~ 999인 길이가 3자리수 값들과 1000이다.

그리고 주어지는 N의 최댓값은 1000이므로 1000의 경우를 따로 설정하면 될 듯하다.

왜냐하면 3자리수를 비교할 때 코드와 네자리수일 때의 코드가 다르기 때문이다.

 

 

그렇다면 위의 사항들을 참고하여 다음과 같이 함수를 만들어보자.

함수에 N이 주어지면 시작한다.

한수의 개수 count는 99개로 바로 초기화하였다.

이는 99이하의 N이 주어진다면 N이 한수의 개수이기 때문이다.

100 이상은 한수의 개수가 99개부터 시작하기에 곧바로 99개로 초기화한 것이다.

 

N이 1000일 때의 출력값은 144로 주어져있으므로 바로 return한다.

N이 1000이 아니고 99 이하일 때는 N의 값을 그대로 return한다. 99이하는 N이 한수의 개수이기 때문이다.

N이 1000이 아니고, 100 이상일 때는 일의 자리수 first, 십의 자리수 second, 백의 자리수 third를 만든다.

그리고 i = 100부터 시작해서 N번까지 반복한다.

반복할 때 first, second, third에 값을 넣어준다.

i = 123이라고 가정해보자.

first = i % 10을 하면, i의 일의 자리수 3이 first에 들어간다.

i/10 을 하면, 일의 자리수 3이 사라지고 i = 12가 된다.

그렇다면 (i / 10) % 10을 하게 된다면 i가 12인 상태의 일의 자리수 2가 나오게 된다.

그래서 second에는 2가 들어가고 third도 마찬가지로 1이 들어가게 된다.

그렇게 각 자리수의 차가 같다면 공차가 성립하므로 한수의 개수 count를 1+해준다.

그리고 마지막엔 count를 return 해준다.

 

 

 

 

1. 함수를 만든다.

2. 만들어 놓은 함수에 N을 넣는다.

3. 출력한다.

 

 

 

풀이1

알고리즘대로 풀었다.