백준 2775: 부녀회장이 될테야 Java(자바) 동적계획법을 이용한 풀이

 

위와 같은 문제를 접근할때는 그림이나 표를 먼저 그려보며 접근하는 편입니다.

표를 보면 알수있듯이 각 집의 거주인원= 아래층같은호+같은층이전호
라는 패턴을 알수있습니다.

 

층과 호를 기준으로 알고리즘을 짰을때 

사람수(x층y호) = 사람수(x-1층y호)+사람수(x층y-1호)호 라는 식으로 접근이 가능합니다!.

 

일반적으로 위방식같은 메서드의 알고리즘은 재귀용법으로 접근하게됩니다.

물론 이렇게 접근해도 정답은 나오지만 ....

 

피보나치 수열 알고리즘을 예시로 위메서드의 특정 값을 구할때

이미 구한 값을 계속 구하게 되는 문제가 있습니다

 

시간복잡도를 증가 시키기때문에 효율적인 알고리즘이라고 생각하지않습니다....

그리하여 배열을 메모리를 이용한 동적 계획법으로 코드를 다시 짜보았습니다

 

사람수[x층][y호] = 사람수[x-1층][y호] + 사람수[x층][y-1] 이런식으로 메모리를 저장하게되면

필요한 값을 다시 계산하는것이 아니라!  저장된값을 다시 가져다 쓰게됩니다.

==

위는 재귀용법

아래는 동적계획법을 사용한 정답 제출시 메모리와 시간복잡도입니다!!

보시다시피 큰 차이를 보이는 편입니다.

 

 

아래에는 전체 정답 코드입니다

import java.util.Scanner;
//부녀회장이 될테야
public class math4 {
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        for (int i=0; i<N; i++){
            int floor = sc.nextInt();
            int room = sc.nextInt();
            //동적계획법
        int people = roomNum(floor,room);
        //재귀용법
       // int people2 =getpeople(floor,room);
           System.out.println(people);
           // System.out.println(people2);
        }
    }
    // 동적계획법
    public static int roomNum(int floor,int room){
        int[][] cache = new int[floor+1][room];
        cache[0][0]=1;
        if(room>1){
            cache[0][1]=2;
        }
        cache[1][0]=1;
        for(int i=0; i<floor+1;i++){
            for (int j=0; j<room;j++){
                cache[i][0]=1;
                cache[0][j]=j+1;
            }
        }
        for (int i=1; i<floor+1;i++){
            for(int j=1; j<room;j++){
                cache[i][j]=cache[i][j-1]+cache[i-1][j];
            }
        }
        return cache[floor][room-1];
    }
    //재귀용법
    public static int getpeople(int floor,int room){
        if(room<2){
            return 1;
        } else if (floor==0) {
            return room;
        }
        return getpeople(floor-1,room)+getpeople(floor,room-1);
    }
}

알고리즘 깃허브/ 백준 자료 :https://github.com/SeungchanKKK/algorithm 에서 코드 참조 하실수있습니다!