티스토리 뷰

Solved.ac Class 완전정복 프로젝트

Class : 2 ~ 2 ++

 


링크

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

 

11050번: 이항 계수 1

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

www.acmicpc.net

문제

접근방법

 이항계수란 '이항식을 이항 정리로 전개했을 때 각 항의 계수이며, 주어진 크기의 (순서 없는) 조합의 가짓수'라고 위키 백과는 정의한다.  자연수 n , 정수 k 에 대한 이항계수는 아래의 그림과 같다.

즉, 조합이다. 조합 구현을 요구하는 문제임을 인식하고 들어가자.

 

풀이

 위의 공식을 만들면 된다. 나는 두가지 방식으로 구현했다.

코드

1. 반복문을 이용하여 구현

import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Main test = new Main();
    }

    public Main(){
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int M = sc.nextInt();

        System.out.println(solution(N,M));
    }

    public int solution(int N,int K){
        int top=1;
        int down =1;
        for (int i = 1 ; i <= K ; i++){
            top *=(N+1-i);
        }

        for (int i = 1 ; i <= K ; i++){
            down *=i;
        }

        return  top/down;
    }
}

 

2. 재귀함수를 이용하여 구현

import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Main test = new Main();
    }

    public Main(){
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int M = sc.nextInt();

        System.out.println(solution(N,M));
    }

    public int solution(int N,int K){
            if(K ==0 || N==K){
            return 1;
        }

        return solution(N-1,K) + solution(N-1,K-1);
    }
}

결과

 재귀함수를 이용할 때에는 입력 범위를 제대로 인지해야한다. 호출 횟수가 비약적으로 늘어나므로, 수치가 클수록 기하 급수적으로 호출횟수가 늘어나니 주의하자.

 


포스팅에 문제가 있거나, 설명이 잘못된 부분 지적 환영합니다.

더 나은 퀄리티의 콘텐츠를 제공할 수 있도록 노력하겠습니다.

읽어주셔서 감사합니다. 

댓글
공지사항
최근에 올라온 글
최근에 달린 댓글
Total
Today
Yesterday
링크
«   2025/02   »
1
2 3 4 5 6 7 8
9 10 11 12 13 14 15
16 17 18 19 20 21 22
23 24 25 26 27 28
글 보관함