[백준] 11051번 이항 계수 2 JAVA (자바) 풀이

문제 11051번 (DP, 수학)

 : 자연수 N과 정수 K가 주어졌을 때 이항 계수 (𝑁𝐾)를 10,007로 나눈 나머지를 구해라

 

 

[입력]

 :  첫째 줄에  N과 K가 주어진다. (1 ≤ N  ≤ 1,000, 0 ≤ K ≤ N)

 

 

[출력]

 

 :  (𝑁𝐾)를 10,007로 나눈 나머지

 

[설명]

 

DP 알고리즘

: 이미 계산된 결과는 별도의 메모리 영역에 저장하여 다시 계산하지 않음으로서 수행 시간 단축시키는 방법

  DP 구현 방법은 일반적으로 Top-down(하향식)과 Bottom-up(상향식)으로 구성된다

 

탑다운 (Top-Down)	보텀업 (Bottom-Up)
작은 크기로 문제를 나눠서 해결	작은 것부터 해결해서 점차 빌드업
메모제이션 (memoization)	타뷸레이션 (tabulation)
일부만 계산해도 답이 나올 때	모두 계산해야 답이 나올 때
재귀	반복문
시간 복잡도 O(n)	시간 복잡도 O(n)

 

1. 이항계수란

출처 https://velog.io/@newdana01

주어진 집합에서 원하는 개수만큼 순서없이 뽑는 조합의 개수를 의미한다

 

(𝑁𝐾) 조합의 특징

• 공식1) (𝑁 0) = (𝑁 𝑁) = 1
  0개를 선택하거나 전부를 선택하는 경우는 1가지 방법뿐이다
  
  
• 공식2) (𝑁 𝐾) = (𝑁-1 𝐾-1) + (𝑁-1 𝐾)
  n개 중에 K를 선택하는 방법은 n번째 원소를 선택할 경우 혹은 선택하지 않는 경우로 나뉜다
  
  1. n번째 원소 택 O =  (𝑁-1 𝐾-1)
  2. n번째 원소 택 X =  (𝑁-1 𝐾)

 

 

 [코드]

import java.io.*;
import java.util.*;
public class Main{
    public static void main(String[] args)throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        int dp[] = new int[N+1];
        
        for(int i=1; i<=N; i++){
            dp[i] = i;
            for(int j=1; j*j<=i; j++){
                if(dp[i]>dp[i-j*j]+1){
                    dp[i] = dp[i-j*j]+1;
                }
            }
        }
        System.out.println(dp[N]);
    }
}

 

 

 [해설]
     

 :  BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    int N = Integer.parseInt(br.readLine());  모든 수

    int K = Integer.parseInt(st.nextToken());  선택할 수
    int dp[] = new int[1000001];  dp 배열 초기화        
        
 :  for(int i=1; i<=N; i++){  N은 1부터 K는 0부터 입력받
            for(int j=0; j<=Math.min(i,K) ;j++){  혹시라도 K가 N을 넘으면 안되니까 N까지만 걍해라
                if(j==0 || j==i){ 
                    dp[i][j] = 1;  조합공식1 이용
                } else{
                    dp[i][j] = (dp[i-1][j-1] + dp[i-1][j])%10007;  조합공식2 이용 
                }        
            }
    }

 :  System.out.println(dp[N][K]);   결과 출력
 
    

 

 

 

 

이제 풀어보러 갈께요 :)

 

 

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

 

 

 

 

 

* 독학으로 익히는 코딩이라 틀린 것이 있을 수 있습니다. 오류가 있다면 댓글을 통해 알려주세요. 감사합니다. *