공부 98일차: 백준 2004번 조합 0의 개수 자바 java

2004 조합 0의 개수

https://www.acmicpc.net/problem/2004

2004번: 조합 0의 개수

 

 

 

---

백준 2004번 문제 조합 0의 개수

---

문제

---

 

 

 

 

---

과정 생각해보기

---

 

우선 조합은 nCr을 말한다

고등학교 때 배웠을 이것..

 

 

https://gimbalja.tistory.com/176

팩토리얼 0의 개수를 구한 문제와 같이 10이 얼마나 나오느냐가 관건인 듯하다

(이번에 1까지 순서대로 가는 게 아니라서 2와 5 중 어느 것이 더 많이 나올지는 알 수 없다)

 

 

문제를 살펴보자면,

n과 m의 크기가 매우 크기 때문에 실제로 nCr값을 구하는 먼저 구해두고 반복하는 문제일 가능성은 적다

n!, (n-r)!, r!가 몇 개의 2, 5를 가지고 있는지 비교한 후 더 작은 값(그래야 그만큼 10이 곱해질 테니까)을 출력하면 될 것 같다

 

 

 

---

정답 인정 코드

---

 

1)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Main {
    static int count;
    
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
        
        int twoCnt = twoCount(n) - twoCount(n-m) - twoCount(m);    //n은 나눠지므로 그때마다 분모가 가진 개수만큼의 2의 개수가 줄어든다
        int fiveCnt = fiveCount(n) - fiveCount(n-m) - fiveCount(m);
        
        if(twoCnt >= fiveCnt) {    //2의 개수가 더 적거나 같으면
            System.out.println(fiveCnt);    //5의 개수 출력(같을 경우 둘 중 아무거나 출력해도 상관없음)
        }else {                    //5의 개수가 더 적으면
            System.out.println(twoCnt);
        }
    }
    
    public static int fiveCount(int n) {
        count = 0;
        while(n >= 5) {
            count += n/5;
            n /= 5;
        }
        return count;
    }
    
    public static int twoCount(int n) {
        count = 0;
        while(n >= 2) {
            count += n/2;
            n /= 2;
        }
        return count;
    }
}
 

 

 

2) 위에서 길이 줄여본 코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;
 
public class Main {
    static int count;
    
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());
        
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
        
        int twoCnt = count(n,2) - count((n-m),2) - count(m,2);    //n은 나눠지므로 그때마다 분모가 가진 개수만큼의 2의 개수가 줄어든다
        int fiveCnt = count(n,5) - count((n-m),5) - count(m,5);
        
        bw.write(String.valueOf(Math.min(twoCnt, fiveCnt)));
        bw.flush();
        bw.close();
        
    }
    
    public static int count(int n, int m) {
        count = 0;
        while(n >= m) {
            count += n/m;
            n /= m;
        }
        return count;
    }
}
 

 

생각해보니까 메서드를 굳이 2, 5로 안 나누고 변수로 두면 될 것 같아서 수정했다

속도도 줄어들까 싶어서 BufferedWriter도 써봤다

 

과정에서 설명한 것을 주석에 다시 풀어 썼다

팩토리얼을 먼저 풀어서 어렵게 느껴지지는 않았다

 

 

 

 

---