[코딩테스트] 백준(BAEKJOON) - 부녀회장이 될테야(Java, 2775번)

안녕하세요~

불금이니 DP문제 한 문제 더 풀어봤습니다.

사실 읽어나 보자하고 픽했는데 바로 풀려서 기분이 좋네요.

간단한  DP문제 같습니다.

 

얼른 코딩테스트의 고수가 되고싶네요..ㅠㅠ

그럼 문제 만나보시죠~

 

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

2775번: 부녀회장이 될테야

네 그렇습니다. 문제가 부녀회장이 될테야라니 신선합니다~

다음은 제 풀이입니다.

 

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

public class Main {
		public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader bf=new BufferedReader(new InputStreamReader(System.in));
		
		int count=Integer.parseInt(bf.readLine());
		
		for(int i=0;i<count;i++)
		{
			int k=Integer.parseInt(bf.readLine());
			int n=Integer.parseInt(bf.readLine());
			
			int[][] people=new int[k+1][n+1];
			
			for(int j=1;j<=n;j++)
				people[0][j]=j;
			
			for(int j=1;j<=k;j++)
			{
				for(int l=1;l<=n;l++)
				{
					people[j][l]=people[j-1][l]+people[j][l-1];
				}
			}
			System.out.println(people[k][n]);
		}
		
	
		
		
	}

}

이번에규칙은 n층의 k호실을 구하려면 n-1층의 k호실의 인원 + n층의 k-1호실의 인원을 더해주면 되겠습니다.

층 수는 0층부터 시작하고 0층 1~k호까지 인원을 1~k로 초기화 해주시면 되겠습니다.

또한 각 층마다 1호실의 인원은 k-1할 값이 없기에 1로 계속 고정되는 듯합니다.

 

이부분 참고해주시면 되겠습니다.

 

또한 문제에서 “a층의 b호에 살려면 자신의 아래(a-1)층의 1호부터 b호까지 사람들의 수의 합만큼 사람들을 데려와 살아야 한다”  는 조건이 있습니다.

 

이 부분을 표로 표현해보면~

측 n층 k호에 거주하려면 n-1층 1호부터 k호까지의 합이 필요하다는 말이되겠습니다.

 

그렇기에 2차원 배열로

array[n층][k호]=array[n-1층][k호]+array[n층][k-1호]가 되겠습니다.

 

네~ 불금 보내셨기를 바라며 마무리하겠습니다.

 

감사합니다. :D