[수학] 백준 - 부녀회장이 될테야

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

2775번: 부녀회장이 될테야

 

-문제해설

다이나믹 프로그래밍을 이용해서 풀었다. d라는 배열을 만들고 행은 k+1까지, 열은 n까지 크기로 만든다.

d = new int[k+1][n];

 

그리고 이중포문을 순회한다. 이때 행을 i, 열을 j라고 하면

i=0일때 즉 0행일 때는 d[0][0], d[0][1], d[0][2]에 각각 1, 2, 3이 들어가도록 한다.

그리고 j=0일 때 즉 0열일 때는 항상 1이므로 d[0][0], d[1][0], d[2][0]에 모두 1이 들어가도록 한다.

 

마지막으로 나머지 행열들에 대해서는 d[i][j] = d[i][j-1] + d[i-1][j] 식으로 값을 넣어준다.

이런 식이 나온 이유는 다음과 같다.

 

입력값 k가 2이고, n이 3일 때 

      0열  1열   2열

2행 | 1     4     10

1행 | 1     3     6

0행 | 1     2     3

 

인데 1행2열의 3의 경우 1행0열 + 0행1열임을 알 수 있다. 나머지 행열도 마찬가지로

2행2열의 10은 2행1열 + 1행2열 = 4 + 6 = 10임을 알 수 있다.

이러한 식을 알아내기 위해 직접 손으로 써보고 식을 도출해낼 수 있었다

 

 

 

-자바

package math;

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

public class BJ2775 {
	private static BufferedWriter bw = 
			new BufferedWriter( new OutputStreamWriter(System.out));
	private static int t, k, n;
	private static int[][] d;

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		t = Integer.parseInt( br.readLine() );
		
		for( int i=0; i<t; i++ ) {
			k = Integer.parseInt( br.readLine() );
			n = Integer.parseInt( br.readLine() );
			
			d = new int[k+1][n];
			int a = 1;
			for( int j=0; j<=k; j++ ) {
				for( int z=0; z<n; z++ ) {
					if( j==0 ) d[j][z] = a++;
					else if( z==0 ) d[j][z] = 1;
					else d[j][z] = d[j][z-1] + d[j-1][z];
				}
			}
			bw.write( d[k][n-1] + "\n" );
			bw.flush();
		}
		bw.close();
		br.close();
	}
}

 

-파이썬

t = int(input())

for _ in range( t ):
    k = int(input())
    n = int(input())
    d = [ [0]*n for _ in range( k+1 ) ]
    
    for i in range( k+1 ):
        for j in range( n ):
            if i==0: d[i][j] = j+1
            elif j==0: d[i][j] = 1
            else: d[i][j] = d[i][j-1] + d[i-1][j]
            
    print( d[k][n-1] )