[Java] 백준 1065번
Input-1
110
Output-1
99
Input-2
210
Output-2
105
Input-3
1000
Output-3
144
문제 풀이
문제 풀이에 앞서 한수가 무엇인지 이해가 잘 되지 않았다.
한수를 알려면 등차수열에 대해서도 알아야 한다.
한수란?
어떤 정수 A의 각 자리수가 등차수열을 이루는 수이다.
등차수열이란?
연속된 두 개의 수의 차이가 일정한 수열을 말한다.
-
그러면 1부터 9까지는 항이 하나뿐인데 등차수열인가?
1~9까지는 하나의 등차수열로 본다. -
그러면 10부터 99까지는 항이 두개인데 등차수열인가?
10의 경우 길이가 2이고 첫번째 항이 1, 두번째 항이 0이며 공차가 -1인 등차수열로 볼 수 있다.
두자리수인 99까지는 모두 등차수열인 것이다.
자 그러면 100부터 주어진 수(N)의 자리수별 차이가 같은 수를 찾으면 된다.
주어진 수가 100 이상이라면 각 자리수를 구하여 첫째항과 둘째항의 차와 둘째항과 셋째항의 차가 같은지 검증하는 로직을 checkHansoo 함수에 작성하였다.
1
2
3
4
5
6
7
8
9
public static int checkHansoo(int n) {
ArrayList<Integer> list = new ArrayList<>();
while(n > 0) { // 주어진 수(n)의 자리수를 구해 list에 저장
list.add(n % 10);
n /= 10;
}
if((list.get(0)-list.get(1)) == (list.get(1)-list.get(2))) return 1;
else return 0;
}
마지막은 결국 주어진 수까지 한수의 개수를 구하는 것이기에 주어진 수(N)만큼 반복하며 한수의 개수를 측정하였다.
1
2
3
4
5
6
7
8
if(n < 100) hs = n; // 1부터 99까지는 모두 한수
else { // 100부터 1000까지
hs = 99;
for (int i=100; i<=n; i++) {
hs += checkHansoo(i);
}
if(n == 1000) hs -= 1;
}
작성코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
import java.io.*;
import java.util.*;
class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
int n = Integer.parseInt(br.readLine());
int hs = 0;
if(n < 100) hs = n;
else {
hs = 99;
for (int i=100; i<=n; i++) {
hs += checkHansoo(i);
}
if(n == 1000) hs -= 1;
}
bw.write(hs + "\n");
bw.flush();
bw.close();
br.close();
}
public static int checkHansoo(int n) {
ArrayList<Integer> list = new ArrayList<>();
while(n > 0) {
list.add(n % 10);
n /= 10;
}
if((list.get(0)-list.get(1)) == (list.get(1)-list.get(2))) return 1;
else return 0;
}
}
회고
- 4673번 셀프넘버 문제에서도 정수의 자리수를 알아야 했는데 이번 1065 문제에서도 동일한 요구사항이 있었던 것으로 보아 자리수 별로 접근하는 방식을 명확하게 알고 있어야 한다고 느꼈다.