백준 2775번 java 부녀회장이 될테야~~! <수학1>

부동산 대란에 내집 마련은 커녕 전세 월세도 힘들어지고 있는 이 시국에 무슨 거주 조건이 다단계마냥 사람들을 끌어와야 하는 거지같은 문제.... 잡소리 그만하고 풀이 들어가겠습니다.

 

k층의 n호에 사려면 k-1층의 1호부터 n호까지 사는 사람의 합을 데려와서 살아야 한다.

그냥 단순히 끄적이면서 규칙을 찾아보도록 하자.

0층 i호에는 i명이 산다고 한다. 

 

0층 1호 = 1명, 0층 2호 = 2명 

1층 1호 = 0층 1호 = 1명

1층 2호 = 0층 1호(1) + 0층 2호(2) = 3명

1층 3호 = 0층 1호(1) + 0층 2호(2) + 0층 3호(3)

0층 1호 + 0층 2호는 1층 2호이므로 1층 2호 + 0층3호가 된다.

이런 규칙이 있다.

k층 n호 = k층 n-1호 + k-1층 n호이렇게 된다.

으음~~?? 아래층을 기준으로 잡고 자기 호수까지 사는 사람들을 더한다.

그럼 아래층이 얼마나 사는지를 알아야 하는데 그렇게 파고들다 보면 0층까지 알아보아야 한다.

 

이것은 재귀함수로 쉽게 풀 수 있겠다.

물론 k, n 이 <= 14 이런 조건이 있기 때문에 for문으로도 간단히 할 수 있겠지만 나는 짧은 코드를 선호한다.

 
import java.util.Scanner;
 
//baekjoon_2775_부녀회장이 될테야
public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        
        int test = sc.nextInt();
        
        for(int t=0; t<test; t++) {
            int k = sc.nextInt();
            int n = sc.nextInt();
            
            System.out.println(el(k,n));
        }
    }
    private static int el(int k, int n) {
        if(n==0)
            return 0;
        else if(k==0)
            return n;
        else {
            return el(k, n-1) + el(k-1, n);
        }
    }
}

우선 테스트 케이스와 k(층) n(호)를 입력한다.

함수로 k, n을 넘겨서 돌리는데

만약 호 수가 0이면 0명이므로 0을 리턴시킨다.

k가 0이면 0층이므로 0층 n호는 n명이 산다고 했다.

그대로 n을 리턴시키면 된다. 여기까지 와야 함수 호출이 끝나고 리턴+리턴+리턴 이렇게 되는 것이다.

 

line 23 : else{} 여기서 재귀함수 수식을 넣으면 된다 k, n-1 + k-1, n 이런식으로..

피보나치나 또 뭐였더라.... 뭐 그런식의 재귀함수 문제를 풀어본 사람은 쉽게 이해가 갈 것 같다.

아무튼 여기서 끄으읏