다이나믹 프로그래밍 알고리즘 C++ / Java / 파이썬 점화식

다이나믹 프로그래밍 알고리즘을 쉬운 문제를 풀며 공부해봅시다.

백준 2775 부녀회장이 될테야 문제를 풀어봅시다.

 

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

2775번: 부녀회장이 될테야

 

 

k와 n의 범위는 1부터 14까지 입니다.

매우 작네요.

느낌상 다이나믹 프로그래밍 알고리즘이라는 생각이 듭니다.

 

엑셀로 그림을 그려봅시다.

배열은 0부터 시작하므로 이해하기 쉽게 0호를 추가합니다.

0층의 i 호에는 i 명이 산다고 하네요.

a층 b호에 사는 사람들은 a-1층의 1호부터 b호까지 사는 사람의 합입니다.

1층에 있는 사람 숫자를 입력하다 보니 벌써 규칙이 나왔네요.

1층 4호 사는 사람은 1층 3호에 있는 숫자에 0층 4호에 사는 사람들 더하면 됩니다.

1층 3호에는 이미 0층 1호 2호 3호에 사는 사람들의 합이 이미 있기 때문입니다.

그래서 붉은 색으로 표시한 2개(6과 4)만 더하면 구하려는 파란 색 10명이 나오게 됩니다.

점화식은 아래와 같습니다.

D[a][b] = D[a-1][b] + D[a][b-1]

그대로 코딩하면 문제가 풀립니다.

 

1번 만 미리 구해놓으면 어떤 테스트케이스가 나오더라도 답이 바뀌지 않습니다.

그리고 0호는 구할 필요가 없어서 반복문은 1호부터 시작합니다.

0호의 값은 0으로 초기화 되어있습니다.

1호의 값들을 구할 때 0호의 값을 참고하게 되고 인덱스 초과없이 자연스럽게 답이 구해집니다.

 

1. C++

#include <stdio.h>

int D[15][15];
int main(){
	int k, n, t;

	for(int i = 0; i < 15; i++){
		for(int j = 1; j < 15; j++){
			if(i == 0){
				D[i][j] = j;
			}else{
				D[i][j] = D[i-1][j] + D[i][j-1];			
			}
		}
	}
	
	scanf("%d", &t);
	
	for(int i = 1; i <= t; i++){
		scanf("%d", &k);
		scanf("%d", &n);
		printf("%d\n", D[k][n]);
	}
}

 

2. JAVA

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

public class Main {
	public static int[][] D = new int[15][15];
	public static void main(String args[]) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		for(int i = 0; i < 15; i++){
			for(int j = 1; j < 15; j++){
				if(i == 0){
					D[i][j] = j;
				}else{
					D[i][j] = D[i-1][j] + D[i][j-1];
				}				
			} 
		}

		int t = Integer.parseInt(br.readLine());
		
		for(int test = 1; test <= t; test++){
			int k = Integer.parseInt(br.readLine());
			int n = Integer.parseInt(br.readLine());
			
			System.out.println(D[k][n]);
		}
	}
}

 

 

3. Python 파이썬

D = [[0]*15 for _ in range(15)]

for i in range(15):
    for j in range(1,15):
        if i == 0:
            D[i][j] = j
        else:
            D[i][j] = D[i-1][j] + D[i][j-1]

t = int(input())

for i in range(t):
    k = int(input())
    n = int(input())

    print(D[k][n])