[JAVA] 알고리즘 문제풀이 - DFS, BFS 기출문제

프로그래머스 기출문제 풀이

조합의 경우수(메모이제이션)

• 설명
  

로 계산합니다.

하지만 여러분은 이 공식을 쓰지않고 다음 공식을 사용하여 재귀를 이용해 조합수를 구해주는 프로그램을 작성하세요.

• 입력 : 첫째 줄에 자연수 n(3<=n<=33)과 r(0<=r<=n)이 입력됩니다.
  
  

• 출력 : 첫째 줄에 조합수를 출력합니다.
  
  

• 풀이

import java.util.*;

public class Main {

    static int[][] chk;

    public int DFS(int ball, int ch) {
        if(chk[ball][ch]>0) return chk[ball][ch];
        if(ball==ch || ch==0){
            return chk[ball][ch] = 1;
        } else {
            return chk[ball][ch] = DFS(ball-1, ch-1) + DFS(ball-1, ch);
        }
    }

    public static void main(String[] args) {
        Main t = new Main();
        Scanner scan = new Scanner(System.in);
        int ball = scan.nextInt();
        int ch = scan.nextInt();
        chk = new int[ball+1][ball+1];

        System.out.println(t.DFS(ball,ch));
    }
}

• 정리
  
  • 첫번째로 문제를 이해하는 것이 관건
    
  • 5개중에 3개의 공을 뽑는다는 예시로 이해했을때 5개의 공에서 5개의 공을 모두 뽑거나, 5개의 공에서 하나도 뽑지 않는 경우의 수는 1개씩만 존재함
    
  • 따라서 n과 r이 동일하거나, r이 0일때까지 재귀함수 실행
    
  • 이때 이미 계산한 데이터를 중복적으로 돌지 않게 하기위해 chk 배열에 계산한 값들을 담아줌
  • 그리고 DFS 진입시 배열에 값이있다면 그대로 리턴