문제
2와 5로 나누어 떨어지지 않는 정수 n(1 ≤ n ≤ 10000)가 주어졌을 때, 각 자릿수가 모두 1로만 이루어진 n의 배수를 찾는 프로그램을 작성하시오.
입력
입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있고, n이 주어진다.
출력
각 자릿수가 모두 1로만 이루어진 n의 배수 중 가장 작은 수의 자리수를 출력한다.
예제 입력 1
3
7
9901
예제 출력 1
3
6
12
요약 : 2와 5로 나누어 떨어지지 않는 정수 N이 주어졌을 때, 1로만 이루어진 N의 배수를 찾는 문제
문제가 발생했다. 처음에 무작정 n을 구하려 하니 시간 초과가 났다. sum을 구하는 시간이 커지면서 발생하는 것이므로 반드시 sum을 구하는 시간을 단축해야 한다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.StringTokenizer;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
PrintWriter pw = new PrintWriter(System.out);
StringTokenizer st = new StringTokenizer(br.readLine());
while (st.hasMoreTokens()) {
int num = Integer.parseInt(st.nextToken());
int cnt = 0;
long sum = 0;
while (true) {
sum += Math.pow(10, cnt);
if ((sum % num) != 0) {
cnt++;
} else {
pw.println(cnt + 1);
st = new StringTokenizer(br.readLine());
break;
}
}
}
pw.close();
}
}
따라서 배수를 실제로 만들지 않고 해결하여야만 했다.
(A+B) % M = ( (A % M) + (B % M) ) % M
(A×B) % M = ( (A % M) × (B % M) ) % M
이것을 이용하여 아래 예시처럼 풀면 된다.
1%7=1
11%7=(1× 10+1)%7=(1%7× 10+1)%7=(1× 10+1)%7=4
111%7=(11× 10+1)%7=(11%7× 10+1)%7=(4× 10+1)%7=6
이런식으로 선례의 식을 이용하여 sum을 구한다.
import java.io.IOException;
import java.util.Scanner;
public class Main {
public static void main(String[] args) throws IOException {
Scanner sc = new Scanner(System.in);
while (sc.hasNext()) {
int n = sc.nextInt();
int num = 0;
for (int i = 1; ; i++) {
num = num * 10 + 1;
num %= n;
if (num == 0) {
System.out.println(i);
break;
}
}
}
}
}
'알고리즘' 카테고리의 다른 글
Sort (0) | 2023.08.03 |
---|---|
[BOJ]1316 그룹단어체커 (0) | 2023.06.22 |
[이론 노트]단순조합과 단순재귀 (0) | 2023.06.19 |
[알고리즘 문제 해결 전략] 20장 문자열 (0) | 2023.06.16 |
[BOJ]4358 생태학 (0) | 2023.06.09 |