[파스칼의 삼각형] b11050_이항계수1

를 구하는 방법은 nCk이다.

nCk를 구하기 위해 파스칼의 삼각형을 이용할 수 있다.

파스칼의 삼각형(Pascal's triangle)은 수학에서 이항계수를 삼각형 모양의 기하학적 형태로 배열한 것이다.

https://ko.wikipedia.org/wiki/%EC%82%BC%EA%B0%81%ED%98%95

파스칼의 삼각형

파스칼의 삼각형의 규칙을 이용하면 nCk = (n-1Ck-1) + (n-1Ck)

주의할점 : k=0, n = k 일 때 경우의 수는 항상 1이다

11050번: 이항 계수 1

package com.pascal_triangle.b11050_이항계수1;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    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 K = Integer.parseInt(st.nextToken());

        // 파스칼의 삼각형 규칙 이용
        // nCk = n-1 C k + n-1 C k-1
        int [][] pascal = new int[N+1][K+1];
        //pascal[0][0] = 1; // 안뽑는것도 하나의 경우의 수
        for (int n = 0; n <= N ; n++) {
            for (int k = 0; k <= K; k++) {
                if(k==n||k==0) pascal[n][k] = 1;  // nC0 nCn 은 경우의 수 한개
                else if(n-1>=0) pascal[n][k] = pascal[n-1][k-1] + pascal[n-1][k];
            }
        }
        System.out.print(pascal[N][K]+" ");

        br.close();
    }
}

import java.util.Scanner;

// 파스칼의 삼각형이란?
// 이항계수를 삼각형 형태로 나타낸 형태이다.. 이를 2차원 DP 테이블로 표현해보자
// 규칙성 : nCk = (n-1)Ck + (n-1)C(k-1)
// -> n개 중에 k개를 뽑는 경우의 수는 n-1개 중에 k개를 뽑는 경우의 수와 n-1개 중에 k-1개를 뽑는 경우의 수를 더한 값
// 주의할 점 : k=0, k=n 일때는 음수가 되기 때문에 이러한 공식이 적용되지 않고 직접 경우의 수 1을 대입해준다.
public class pascals_triangle {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int K = sc.nextInt(); // (x+y) N제곱일 때, x의 k제곱 * y의 n-k제곱의 계수 구하기
                                // 즉, Math.pow(x+y,N) 일 때, Math.pow(x,k)*Math.pow(y,n-k)의 계수
        int [][] pascal = new int[N+1][K+1];
        //pascal[0][0] = 1;   // 0개중에 0개를 뽑는 것도 1개의 경우의 수
        for (int r = 0; r <= N ; r++) {
            for (int c = 0; c <= r ; c++) {
                if(c==0||c==N) {    // k=0, k=N일 때는 경우의 수 1
                    pascal[r][c] = 1;
                }else if(r-1>=0){
                    pascal[r][c] = pascal[r-1][c] + pascal[r-1][c-1];
                }
                System.out.print(pascal[r][c]+" ");
            }
            System.out.println();
        }

        sc.close();
    }
}