https://www.acmicpc.net/problem/1065
1065번: 한수
어떤 양의 정수 X의 각 자리가 등차수열을 이룬다면, 그 수를 한수라고 한다. 등차수열은 연속된 두 개의 수의 차이가 일정한 수열을 말한다. N이 주어졌을 때, 1보다 크거나 같고, N보다 작거나 ��
www.acmicpc.net
생각 :
이 문제는 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);
}
}
}
'JAVA 알고리즘 ' 카테고리의 다른 글
SWEA - 격자판의 숫자이어붙이기 (0) | 2020.08.02 |
---|---|
백준 - 미세먼지 안녕 (0) | 2020.07.28 |
BOJ 7576번 - 토마토 (1) | 2020.07.08 |
SWEA 2805번 - 농작물 수확하기 (1) | 2020.06.27 |
SWEA 8104번 - 조 만들기 (0) | 2020.06.27 |