문제 번호 2775번 : 부녀회장이 될테야 - JAVA [자바]

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

2775번: 부녀회장이 될테야

 

문제 설명

 

문제는 입력된 층수와 호수에 몇 명의 사람이 필요한지 구하는 문제입니다. 이때 중요한 건 해당 층수와 호수에 밑 층수에 해당 호수의 사람 수만큼 더한 사람이 필요하다는 것입니다. 

이 말만 들어서는 이해가 잘 안됩니다. 그림으로 확인해 보겠습니다. 문제를 모두 적용했을 때 각 호수의 사람 수를 적은 표입니다.

해당 그럼을 보시면 총 14층, 14호까지 되어 있습니다. 이렇게 14층과 14호를 마지막으로 둔 이유는 문제에 해당 조건 때문입니다.

k는 층수를 n는 호수를 나타내는데 이는 14를 넘어갈 수 없다고 되어 있습니다. 문제를 풀 때 2차 배열로 15개의 배열로 만들면 될 것 같습니다.

 

그럼 3층의 6호를 구하는 방법을 살펴보겠습니다.

다음 그림처럼 3층의 6호 사람 수를 구하기 위해서는 초록색의 사람 수를 모두 더해야 합니다.

즉 1+4+10+20+35+56 = 126 이 되는 것이죠. 2층의 1호~6호까지의 모든 사람 수를 구해라 이게 문제의 의미입니다.

근데 여기서 생각해 보면 2층의 1호~5호까지는 3층의 5호에서 이미 계산이 되어 있습니다. 그래서 사실 다음처럼 계산할 수도 있습니다.

3층의 5호(70) + 2층의 6호(56) = 126으로 같은 계산이 나옵니다.

이제 문제를 푸는 입장에서 어떤 식으로 접근하면 좋을까요?

저희가 아는 건 해당 층수와 호수입니다. 그렇다면 저희가 알아야 하는 값은 같은 층수의 호수-1의 값 같은 호수의 층수-1의 값을 알면 됩니다. 하지만 그 값만 바로 딱 구할 수 있는 식은 있을 수도 있겠지만 수학 전공이 아닌 저는 층수와 호수만을 가지고 값을 구할 수 없을 것 같습니다.(어떻게 수열로 할 수 있을 거 같기도 한데 찾다가 포기했습니다..ㅎ) 그래서 3층의 6호의 사람 수를 구하기 위해서는 다음 과 같은 모든 수를 알아내야 합니다.

초록색으로 된 모든 값을 차례대로 구하다 보면 결국에는 3층의 6호의 값도 알 수 있습니다. 

수학 전공이 아니어서 식을 세우시는 못하지만 컴퓨터가 대신 for 문으로 빠르게 계산하게 해 줄 수는 있습니다.😊

 

문제 풀기

 

접근 방법은 이준 for 문으로 호수-1과 층수-1을 더해 차근차근 밑에서부터 이차 배열을 채워나가는 것을 목적으로 접근하면 됩니다.

그럼 먼저 이차 배열이 있어야겠죠

int[][] peoCount = new int[15][15];

0층부터 14층까지 15개의 층 14개의 호수이지만 확실하게 하기 위해서 15개 15개의 이차 배열을 만들겠습니다.(int형 이차 배열은 빈값은 모두 0으로 채워서 크게 상관이 없습니다.)

 

그 후에 먼저 1층과 1호의 수를 채워 줍니다.

for(int i = 0; i < peoCount.length; i++) {
	peoCount[i][0] = 1;
	peoCount[0][i] = i+1;
}

그리고 이중 for 문으로 해당 층수와 호수만큼 돌려 수를 구하면 됩니다.

(충수-1) + (호수-1) = 해당 층수와 호수의 사람 수

공식을 사용하여 for 문에 넣어줍니다. 그럼 필요한 만큼의 수가 모두 구해지면서 마지막 해당 호수와 층수의 사람 수도 구할 수 있게 됩니다.

for(int i = 1; i <= k; i++) {
    for(int j = 1; j < n; j++) {
        //System.out.println("peoCount[" + i + "][" + (int)(j-1) + "] : " + peoCount[i][j-1]);
        //System.out.println("peoCount[" + (int)(i-1) + "][" + j + "] : " + peoCount[i-1][j]);
        peoCount[i][j] = peoCount[i][j-1] + peoCount[i-1][j];
        //System.out.println("peoCount[" + i + "][" + j + "] : " + peoCount[i][j]);
    }
}

마지막으로 정답을 출력합니다.

System.out.println("result : " + peoCount[k][n-1]);

이때 층수는 0층부터 시작해서 상관없지만 호수는 1층부터 시작함으로 -1을 넣어줍니다.(배열은 0부터 시작합니다.)

 

정답

 

import java.util.*;

public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
		
		int t = sc.nextInt();
		
		for(int test = 0; test < t; test++) {
			int k = sc.nextInt();//층수 
			int n = sc.nextInt();//호수 
			
			int[][] peoCount = new int[15][15];
			
			for(int i = 0; i < peoCount.length; i++) {
				peoCount[i][0] = 1;
				peoCount[0][i] = i+1;
			}
			
			for(int i = 1; i <= k; i++) {
				for(int j = 1; j < n; j++) {
					//System.out.println("peoCount[" + i + "][" + (int)(j-1) + "] : " + peoCount[i][j-1]);
					//System.out.println("peoCount[" + (int)(i-1) + "][" + j + "] : " + peoCount[i-1][j]);
					peoCount[i][j] = peoCount[i][j-1] + peoCount[i-1][j];
					//System.out.println("peoCount[" + i + "][" + j + "] : " + peoCount[i][j]);
				}
			}
			System.out.println(peoCount[k][n-1]);
		}
    }
}

마지막에 test 개수로 for문을 한 번 더 감싸줬습니다.

 

주희가 꼭 부녀회장이 되었으면 좋겠네요😁 

곧 대선인데 투표 꼭 합시다~