백준 2775: 부녀회장이 될테야(java/C)

문제

 

풀이

 

2차원 배열을 사용해 풀 수 있을 것 같다

 

우선 k층 n호의 사람 수를 정리해 보면 아래와 같다.

각 호실 별 사람 수를 저장할 int형 2차원 배열 aptArr를 설정했으며

 

층수에 관계없이 1호는 항상 1명이 거주하고, 0층의 k호에는 k명이 거주한다.

그 외의 경우 (같은 층 바로 전 호의 사람 수) + (아래 층 같은 호의 사람 수)인 것을 알 수 있으므로

aptArr[0][n]=n;		//0층 n호는 n명
aptArr[k][1]=1;		//1호는 항상 1명
aptArr[k][n]=aptArr[k][n-1]+aptArr[k-1][n];

로 정리할 수 있다.

 

for문을 사용하여 aptArr 배열을 먼저 완성한 다음, T 횟수만큼 k와 n을 입력받아 해당하는 호실의 사람을 꺼내 오는 방식으로 풀이하였다.

 

[JAVA]

실행 시간을 줄이기 위해 Scanner 대신 BufferedReader를 사용

Scanner 사용하려면 main함수 헤더에서 throws IOException 지우고 사용하면 된다.

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

public class Main {
	public static void main(String[] args) throws IOException{
		BufferedReader in=new BufferedReader(new InputStreamReader(System.in));
		
		int[][] aptArr=new int[15][15];
		
		for(int i=0; i<15; i++) {
			aptArr[0][i]=i;
			aptArr[i][1]=1;
		}
		for(int k=1; k<15; k++) {
			for(int n=2; n<15; n++) {
				aptArr[k][n]=aptArr[k][n-1]+aptArr[k-1][n];
			}
		}
		
        int T=Integer.parseInt(in.readLine());
		for(int i=0; i<T; i++) {
			int k=Integer.parseInt(in.readLine());
			int n=Integer.parseInt(in.readLine());
			System.out.println(aptArr[k][n]);
		}
	}
}

 

[C]

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>

int main(void) {
	int T, k, n;

	int aptArr[15][15];
	for (int i = 0; i < 15; i++) {
		aptArr[0][i] = i;
		aptArr[i][1] = 1;
	}
	for (int k = 1; k < 15; k++) {
		for (int n = 2; n < 15; n++) {
			aptArr[k][n] = aptArr[k][n - 1] + aptArr[k - 1][n];
		}
	}

	scanf("%d", &T);
	for (int i = 0; i < T; i++) {
		scanf("%d", &k);
		scanf("%d", &n);
		printf("%d\n", aptArr[k][n]);
	}
    
    return 0;
}