문제
자연수 A가 자연수 B의 약수이기 위해서는 B가 A로 나누어 떨어져야 한다.
초등학생인 정우는 오늘 배운 약수라는 개념에 홀딱 반해버렸다.
집에 가는 길에 계속 약수만 떠올리던 정우는 엄청난 사실을 발견했다!
숫자 2는 2 앞에 어떤 숫자를 붙여도 2를 약수로 가졌다.
5 역시 5 앞에 어떤 숫자를 붙여도 5를 약수로 가졌다.
예를 들어 숫자 3827를 5 앞에 붙이면 38275가 되며, 이는 5를 약수로 가진다.
정우는 이런 특별한 성질을 가지는 자연수를 최약수 라고 명명했다.
즉, 최약수란 앞에 어떤 숫자를 붙여도 자신을 약수로 가져야 한다.
정우는 최약수의 종류가 궁금했다!
정우를 도와서 주어지는 숫자 X 보다 작거나 같은 최약수의 개수를 구해주자.
풀이방법
문제에서 말하는 최약수는 한 자리 높은 수의 값을 1로 만들 수 있으면 된다.
한 자리 높은 수의 값을 1을 만든다는 말은 최약수 x가 있을 때,
최약수 x는 1x가 될 수 있다. 또한 최약수 x는 2x가 될 수도 있다. 같은 방식으로 3x, 4x, ..., 3827x까지 가능하다.
이러한 방식으로 10, 100, 1000, 10000을 만들 수 있는 최약수를 찾는다.
10을 만들 수 있는 최약수 x : {1, 2, 5} - 3개
100을 만들 수 있는 최약수 x : {10, 20, 25, 50} - 4개
1000을 만들 수 있는 최약수 x {100, 125, 200, 250, 500} - 5개
1000이상부터는 최약수의 패턴이 모두 같다.
10000은 1000, 1250, 2000, 2500, 5000,
100000은 10000, 12500, 20000, 25000, 50000...
즉, 주어진 입력 x가
1자리 일 때는 a
2자리일 때는 3 + a
3자리일 때는 3 + 4 + a
4자리일 때는 3 + 4 + 5 + a
n(n >= 3)자리일 때는 3 + 4 + 5(n - 3) + a이다.
a는 x가 n자리 일때, n자리 중 최약수의 개수이다.
소스코드
package samsung;
import java.util.*;
public class s_7854 {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int[] one = {1, 2, 5};
int[] two = {20, 25, 50, 100};
int[] three = {100, 125, 200, 250, 500};
int tc = sc.nextInt();
for(int t = 1; t <= tc; t++) {
int cnt = 0;
String s = sc.next();
int n = s.length();
if(n == 1) {
int num = Integer.parseInt(s);
for(int i = 0; i < one.length; i++) {
if(num >= one[i]) cnt++;
else break;
}
}
else if(n == 2) {
cnt += 3;
int num = Integer.parseInt(s);
for(int i = 0; i < two.length; i++) {
if(num >= two[i]) cnt++;
else break;
}
}
else {
for(int i = 0; i < n-1; i++) {
if(i == 0) cnt += 3;
else if(i == 1) cnt += 4;
else cnt += 5;
}
String tmp = s.substring(0, 3);
int num = Integer.parseInt(tmp);
for(int i = 0; i < three.length; i++) {
if(num >= three[i]) cnt++;
else break;
}
}
System.out.println("#" + t + " " + cnt);
}
}
}
'Problem Solving > SWEA' 카테고리의 다른 글
[SWEA] 4613. 러시아 국기 같은 깃발 (0) | 2020.03.07 |
---|---|
[SWEA] 3347. 올림픽 종목 투표 (0) | 2020.03.07 |
[SWEA] 1238. [S/W 문제해결 기본] 10일차 - Contact (1) | 2020.03.06 |
[SWEA] 6719. 성수의 프로그래밍 강좌 시청 (0) | 2020.03.06 |
[SWEA] 1868. 파핑파핑 지뢰찾기 (0) | 2020.03.06 |
댓글