시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율
| 2 초 | 128 MB | 74708 | 35350 | 29587 | 47.045% |
문제
N! 에서 뒤에서부터 처음 0이 아닌 숫자가 나올 때까지 0의 개수를 구하는 프로그램을 작성하시오.
입력
첫째 줄에 N이 주어진다. (0 ≤ N ≤ 500)
출력
첫째 줄에 구한 0의 개수를 출력한다.
풀이✔
1️⃣ 문제 분석하기
- N! 에서 뒤에서부터 처음 0이 아닌 숫자가 나올 때 까지 0의 개수를 구하는 프로그램을 작성해야 함.
- 계산된 팩토리얼의 뒤에서부터 한 자리씩 확인합니다.
- 0이 아닌 숫자가 나올 때까지 0의 개수를 세어줍니다.
- 예를들어 10! ⇒ 3688800 이면은
- → 0의 개수는 2개이다.
- 팩토리얼의 값에서 0의 개수를 세는 로직을 짜는게 방법!
2️⃣ 요구 조건 구현하기
- 첫째 줄에 N이 주어짐
- N에 대한 0의 개수를 출력해야함.
3️⃣ 슈도 코드
Bufferedreader 생성
변수 N = 입력받기
long fact= factorial(N);
int count = countZero(fact);
count 출력
countZero(int n) {
로직 작성
}
4️⃣ 코드 작성
package Algorithm_step;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class B1676 {
public static void main(String[] args) throws IOException {
BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(bf.readLine());
long fact = factoiral(N);
int count = CountZero(fact);
System.out.println(count);
}
//0세기
private static int CountZero(long number) { //3688800
int countZero = 0;
while (number % 10 == 0) {
countZero++;
number /= 10;
}
return countZero;
}
//팩토리얼
private static long factoiral(int n) {
if(n<=1) {
return 1;
} else {
return n * factoiral(n-1);
}
}
}
while (number % 10 == 0) {
countZero++;
number /= 10;
}
1번
number = 3628800
3628800 % 10 == 0(나머지)
성립이 되므로 countZero 1증가
3628800 / 10 = 362880
2번
number = 362880
362880 % 10 == 0(나머지)
성립이 되므로 countZero 1증가
362880/10 = 36288
3번
number = 36288
36288 % 10 == 8(나머지)
성립이 안된다.
while문 종료
이렇게 풀면은 문제 자체는 풀리지만 백준에서는 “시간 초과” 가 뜹니다.
그래서 다른 방법으로 접근을 해보았습니다.
애초에 접근을 0이 아닌 숫자가 나올 때 까지 0의 개수를 구하는 것 이니
중간에 0이 낀거는 상관 안써두 된다.
소인수 분해를 통해 풀 수 있었습니다.
10은 2*5 이다.
2는 5보다 작은 수여서 연속된 수를 곱하게 되면 자연스레 모든 값들의 소인수 분해들은 2의 개수가 5의 개수보다 많다.
기본적으로 5의 개수에 따라 0이 변화한다고 보면 된다.
그러므로 5를 나누면서 누적합을 구하는 로직을 짜야한다.
int count = 0;
while (num >= 5) {
count += num / 5;
num /= 5;
}
로직을 교체 해주고 팩토리얼을 따로 구하는 로직을 빼면 시간초과가 뜨지 않는다. 자세한건 아래 설명이 있습니다.
결과
package Algorithm_step;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class B1676 {
public static void main(String[] args) throws IOException {
BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(bf.readLine());
int count = CountZero(N);
System.out.println(count);
}
//0세기
private static int CountZero(long number) { //3688800
int countZero = 0;
while (number >= 5) {
countZero += number/5;
number/=5;
}
return countZero;
}
}
사실상 팩토리얼을 구하고 또 계산을 할 필요도 없었습니다.
N이 10이라고 가정을 하면
10/5 ⇒ 2 , 바로 2가 0을 개수라고 생각하면 된다.
15/5 ⇒ 3, 3이 뒤에서 부터 센 0을 개수 이다.
위 사진에서 0의 개수를 파악하면서 알 수 있었습니다. 만약에
전체에 0을 개수를 세는 로직을 짜야했으면 다른 코드가 나왔을 것 입니다.
5️⃣ 핵심 파악하기
0을 구하거나, 몫 나머지 를 구하는 문제가 나온다면
%10, /10을 통해서 구하는 방법을 처음으로 떠올려야 하며
10을 소인수 분해시 2,5 라는 것을 염려해두고 이 방법을 활용한 로직 또한
생각을 해야 한다.