[백준알고리즘/기본 수학 1단계] 2775번 문제 : 부녀회장이 될테야

안녕하세요

백준 알고리즘 단계별로 풀어보기 8단계 2775번 문제 부녀회장이 될테야를 풀어봤습니다

이번 문제는 알고리즘에 대해서는 어떻게 할지 금방 해결이 되었는데 알고리즘을 프로그램을 구현을 하려니 머리가 아팠던 문제였습니다

제가 풀은 방법에 대해서 설명하겠습니다

 

---

문제 링크입니다

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

2775번: 부녀회장이 될테야

 

문제

평소 반상회에 참석하는 것을 좋아하는 주희는 이번 기회에 부녀회장이 되고 싶어 각 층의 사람들을 불러 모아 반상회를 주최하려고 한다.

이 아파트에 거주를 하려면 조건이 있는데, “a층의 b호에 살려면 자신의 아래(a-1)층의 1호부터 b호까지 사람들의 수의 합만큼 사람들을 데려와 살아야 한다” 는 계약 조항을 꼭 지키고 들어와야 한다.

아파트에 비어있는 집은 없고 모든 거주민들이 이 계약 조건을 지키고 왔다고 가정했을 때, 주어지는 양의 정수 k와 n에 대해 k층에 n호에는 몇 명이 살고 있는지 출력하라. 단, 아파트에는 0층부터 있고 각층에는 1호부터 있으며, 0층의 i호에는 i명이 산다.

 

입력

첫 번째 줄에 Test case의 수 T가 주어진다. 그리고 각각의 케이스마다 입력으로 첫 번째 줄에 정수 k, 두 번째 줄에 정수 n이 주어진다

 

출력

각각의 Test case에 대해서 해당 집에 거주민 수를 출력하라.

 

 

---

 

 

문제 풀이

먼저 층 수에 사는 사람의 인원 수 입니다

각 층의 1호에는 한 명의 사람만 살고 있습니다

0층의 경우 N호수만큼 사람이 살고 있습니다

여기까지는 구하는데 어려움이 없습니다

1	11	66	286	1001	3003	8008	19448	43758	92378
1	10	55	220	715	2002	5005	11440	24310	48620
1	9	45	165	495	1287	3003	6435	12870	24310
1	8	36	120	330	792	1716	3432	6435	11440
1	7	28	84	210	462	924	1716	3003	5005
1	6	21	56	126	252	462	792	1287	2002
1	5	15	35	70	126	210	330	495	715
1	4	10	20	35	56	84	120	165	220
1	3	6	10	15	21	28	36	45	55
1	2	3	4	5	6	7	8	9	10

각 층 수에 사는 인원 수는 위의 표처럼 인원 수가 살게됩니다

 

인원수 표를 잘 보면 이차원 배열로 나눴을 때

People[I][J] = People[I - 1][J] + People[I][J - 1] 이 됩니다

이 공식을 계속해서 나열해서 K층 N호의 인원 수를 구해주면 됩니다

 

---

 

첫 번째 방법은 재귀함수를 사용해서 풀었습니다

재귀함수를 사용 반복해서 N-1만큼, K-1만큼 값을 더해줍니다

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

public class Main {
	public static void main(String[] args) throws IOException {
		// BR, SB, Count 변수 선언 및 입력
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));			
		StringBuilder sb = new StringBuilder();		
		int count = Integer.parseInt(br.readLine());
		
		// Count만큼 반복
		for(int i = 0; i < count; i++) {
			int K = Integer.parseInt(br.readLine());
			int N = Integer.parseInt(br.readLine());
			
			// 인원 수 계산 메서드 호출
			sb.append(PeopleNumber(K, N)).append("\n");
		}
		
		System.out.print(sb); // 결과 출력
	}
	
	// 인원 수 계산 메서드 선언
	static int PeopleNumber(int K, int N)
	{		
		// N이 0인 경우 0으로 return
		if(N == 0)
			return 0;
		// K가 0인 경우 N으로 return
		else if(K == 0)
			return N;
		// 재귀함수를 사용 계속해서 더해준다
		else 
			return PeopleNumber(K, N - 1) + PeopleNumber(K - 1, N);
	}
}

 

---

 

두 번째 방법은 이차원 배열로 위의 알고리즘을 각 배열에 데이터를 입력해서 그 데이터를 호출해서 결과값을 출력해줍니다

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

public class Main {
	public static void main(String[] args) throws IOException {
		// BR, SB, Count 변수 선언 및 입력
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));		
		StringBuilder sb = new StringBuilder();		
		int count = Integer.parseInt(br.readLine());
		
		// 인원 수를 미리 배열로 계산
		int[][] floor = new int[15][15];
		
		for(int i = 1; i < 15; i++)
		{
			floor[0][i] = i;
		}
		
		for(int i = 1; i < 15; i++) {
			for(int j = 1; j < 15; j++) {
				if(j == 1)
					floor[i][j] = 1;
				else
					floor[i][j] = floor[i - 1][j] + floor[i][j - 1];
			}
		}
		
		// count만큼 결과 입력
		for(int i = 0; i < count; i++) {
			int K = Integer.parseInt(br.readLine());
			int N = Integer.parseInt(br.readLine());
			
			sb.append(floor[K][N]).append("\n");
		}
		
		System.out.print(sb); // 결과 출력
	}
}

 

---

 

세 번째 방법은 다른 공식을 사용해서 구합니다

밑의 방법을 대략 그려봤습니다!

예를 들어 120의 값을 구하려면 밑밑의 데이터의 56 + (21 x 2) + (6 x 3) + (1 x 4) 이렇게 해서 구하는 방법이 하나 더 있습니다

이 방법을 이용해서 구현한 방법입니다

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

public class Main {
	public static void main(String[] args) throws IOException {
		// BR, SB, Count 변수 선언 및 입력
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));			
		StringBuilder sb = new StringBuilder();		
		int count = Integer.parseInt(br.readLine());
		
		// Count만큼 반복
		for(int i = 0; i < count; i++)
		{
			int K = Integer.parseInt(br.readLine());
			int N = Integer.parseInt(br.readLine());

			// 인원 수 계산 메서드 호출
			sb.append(PeopleNumber(K, N)).append("\n");
		}
		
		System.out.print(sb); // 결과 출력
	}
	
	// 인원 수 계산 메서드 선언
	static int PeopleNumber(int K, int N)
	{		
		int[] HoNum = new int[N+1];
		int sum = 0;
		
		if(K == 1)
		{
			for(int j = 1; j <= N; j++)
				sum += j;
		}
		else
		{
			for(int j = 0; j < N + 1; j++)
				HoNum[N - j] = 1 + j;
			
			for(int j = 2; j < K; j++) {
				for(int k = 1; k < N; k++) {
					HoNum[N-k] += HoNum[N-k+1];
				}
			}
			
			for(int j = 0; j <= N; j++)
				sum += HoNum[j] * j;
		}
		
		return sum;
	}
}

 

여기까지 세 가지 방법으로 풀어봤습니다

이제 속도비교를 해보겠습니다

 

---

 

속도 비교

1번 : 재귀함수 방법

2번 : 이차원 배열 방법

3번 : 다른 공식 적용

각 방법으로 푼 시간과 메모리입니다

 

2번 방식이 메모리와 시간이 제일 최적화가 됐네요 ㅠ

3번 방식으로 풀었는데 시간 더 줄일려고 하다보니 답안을 많이 제출하게 됐습니다 ㅎㄷ;

 

이상 백준 알고리즘 2775번 부녀회장이 될테야를 풀은 내용이었습니다

 

다음 문제 : 2021.05.26 - [알고리즘/알고리즘JAVA] - [백준알고리즘/기본 수학 1단계] 2839번 문제 : 설탕 배달

이전 문제 : 2021.05.25 - [알고리즘/알고리즘JAVA] - [백준알고리즘/기본 수학 1단계] 10250번 문제 : ACM 호텔