day7 백준 2775번 : 부녀회장이 될테야 [Java]

문제출처

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

2775번: 부녀회장이 될테야

재귀로 풀었는데 시간초과가 나올까봐 좀 걱정을 했다...

k층 n호에 사는 사람의 수는 k-1층 n호의 사는 사람수와 k층 n-1호에 사는 사람의 수를 더한것과 같기 때문에 계속 재귀 재귀 재귀해서 풀면 되겠다고 생각함.

0층에는 1 2 3 4 5 ... 이런식으로 사람이 늘어나고 각층의 1호에는 사람이 1명밖에 안살기 때문에 미리 채워놨음

import java.util.Scanner;
public class day007_Q2775 {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int T = sc.nextInt();
		
		for(int i = 0; i < T; i++) {
			int k = sc.nextInt();
			int n = sc.nextInt();
			k++;
			int[][] apt = new int[k][n];
			
			int a = 1;
			for(int j = 0; j < k; j++) {
				apt[j][0] = 1;
			}
			for(int j = 0; j < n; j++) {
				apt[0][j] = a++;
			}
			
			int answer = calc(apt, k - 1, n - 1);
			
			System.out.println(answer);
		}
		sc.close();
	}
	
	public static int calc(int [][] apt, int k, int n) {
		if(apt[k - 1][n] == 0) {apt[k - 1][n] = calc(apt, k - 1, n);}
		if(apt[k][n - 1] == 0) {apt[k][n - 1] = calc(apt, k, n - 1);}
		
		return apt[k - 1][n] + apt[k][n - 1];
	}

}

 

결과는 런타임 에러다

처음에는 14 14 같이 큰 수에서 오류가 나는건가?했는데

1 1같이 작은데서 오류가 났다..

 

중간에 k++이 있어서 0층을 구현하는건 괜찮은데

재귀함수의 k-1이나 n-1같은데서 인덱스가 0일 경우에 거기서 더 마이너스가 돼서 오류가 발생했다.

 

import java.util.Scanner;
public class day007_Q2775 {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int T = sc.nextInt();
		
		for(int i = 0; i < T; i++) {
			int k = sc.nextInt();
			int n = sc.nextInt();
			k++;
			int[][] apt = new int[k][n];
			
			int a = 1;
			for(int j = 0; j < k; j++) {
				apt[j][0] = 1;
			}
			for(int j = 0; j < n; j++) {
				apt[0][j] = a++;
			}
			
			int answer = apt[k - 1][n - 1];
			if(answer == 0) {
				answer = calc(apt, k - 1, n - 1);
			}
			
			System.out.println(answer);
		}
		sc.close();
	}
	
	public static int calc(int [][] apt, int k, int n) {
		if(apt[k - 1][n] == 0) {apt[k - 1][n] = calc(apt, k - 1, n);}
		if(apt[k][n - 1] == 0) {apt[k][n - 1] = calc(apt, k, n - 1);}
		
		return apt[k - 1][n] + apt[k][n - 1];
	}

}

 

 

 

조건문을 하나 추가해주니 맞았다!