[백준22775/JAVA] 부녀회장이 될테야

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

2775번: 부녀회장이 될테야

 

풀이

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

public class Main {

    static int getValue(int k, int n){
        if(k==0) return n;
        else if(n==1) return 1;
        else return (getValue(k,n-1) + getValue(k-1,n));
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int t = Integer.parseInt(br.readLine());

        for(int i=0;i<t;i++){
            int k = Integer.parseInt(br.readLine());
            int n = Integer.parseInt(br.readLine());

            System.out.println(getValue(k,n));
        }

    }
}

 

설명

k층의 n호에 사는 사람의 수를 구하는 문제이다.

k층의 n호에 사는 사람의 수는 k-1층의 1호부터 k-1층의 n호까지 사는 사람들의 수를 모두 더한 값이다.

 

- k층의 n호에 사는 사람의 수를 구하기 위해서는 k-1층에 사는 사람들을 알아야 하고, k-1층에 사는 사람을 알려면 k-2층에 사는 사람을 알아야 한다.

 이처럼 특정 값을 알기 위해서는 결국 0층에 사는 사람의 값을 구해서 k층까지 재귀적으로 값을 구해야한다.

  

또한 0층의 n호에 사는 사람은 n명이다.

- 이를 통해 0층에 사는 n호 사람의 수를 구할수 있다. ( 층(k)이 0이면, 호(n)에 사는 사람의 수는 n이다)