[JAVA] 알고리즘 문제풀이 - DFS, BFS 기출문제 (수열 추측하기)

DFS, BFS 기출문제 풀이

수열 추측하기

설명 : 가장 윗줄에 1부터 N까지의 숫자가 한 개씩 적혀 있다. 그리고 둘째 줄부터 차례대로 파스칼의 삼각형처럼 위의 두개를 더한 값이 저장되게 된다.

예를 들어 N이 4 이고 가장 윗 줄에 3 1 2 4 가 있다고 했을 때, 다음과 같은 삼각형이 그려진다.

N과 가장 밑에 있는 숫자가 주어져 있을 때 가장 윗줄에 있는 숫자를 구하는 프로그램을 작성하시오.

단, 답이 여러가지가 나오는 경우에는 사전순으로 가장 앞에 오는 것을 출력하여야 한다.

입력 : 첫째 줄에 두개의 정수 N(1≤N≤10)과 F가 주어진다. N은 가장 윗줄에 있는 숫자의 개수를 의미하며 F는 가장 밑에 줄에 있는 수로 1,000,000 이하이다.
출력 : 첫째 줄에 삼각형에서 가장 위에 들어갈 N개의 숫자를 빈 칸을 사이에 두고 출력한다. 답이 존재하지 않는 경우는 입력으로 주어지지 않는다.
풀이 답안

import java.util.*;

public class Main {

    static String result = "";
    static int num, total;
    static int[][] chk;
    static int[] chk2, arr;
    public int progression(int a, int b){
        if(chk[a][b]>0) return chk[a][b];
        if(a==b || b==0) return chk[a][b]=1;
        else {
            return chk[a][b] = (progression(a-1,b-1)+(progression(a-1,b)));
        }
    }

    public void solution(int idx, int sum) {

        if(idx>num || total<sum || (total==sum && idx<num)) return;
        if(total==sum && idx==num) {
            for (int i : arr) {
                result += i+" ";
            }
        } else {
            for(int i=1; i<=num; i++){
                if(chk2[i]==0){
                    chk2[i] = 1;
                    arr[idx] = i;
                    solution(idx+1, sum+chk[num-1][idx]*i);
                    chk2[i] = 0;
                    if(!result.equals("")) return;
                }
            }
        }
    }

    public static void main(String[] args) {

        Main main = new Main();
        Scanner scan = new Scanner(System.in);
        num = scan.nextInt();
        total = scan.nextInt();

        arr = new int[num];
        chk = new int[num+1][num+1];
        chk2 = new int[num+1];

        for(int i=0; i<=num; i++){
            main.progression(num, i);
        }

        main.solution(0, 0);
        System.out.print(result);
    }
}

정리
- 일단 크게 두가지 작업을 하는 방식으로 구분해서 구현했다
  1. 수열에 따른 결과 값을 구하는 메소드
  2. 1에서 찾은 값과 동일한 수열 순서를 찾는 메소드
- 수열은 직전에 풀었던 문제에서 풀었던 기억이 있어 동일한 방식으로 풀이함 (https://ejimdev.github.io/javatest/challenges70/)
- 미리 이차원배열을 만들어서 위에서 구해진 수열값들을 미리 담아두고
- 솔루션 함수에서는 레벨(인덱스)와 합계를 매개변수로 넘겨줌. 이때 초기값은 둘다 0
- 인덱스가 범위를 넘어서거나, 합계가 지정범위를 넘어가거나, 합계가 같으나 인덱스 도달을 못했을시 의미없으니 return
- 지정 수만큼 반복을 돌게 하되 ,체크 배열을 만들어서 이미 앞에서 담아둔 순번은 체크하지 않도록 함
- 아직 방문한적 없는 수라면 결과배열의 해당레벨에 담아주고
- 재귀함수에 레벨값+1, 합계에 기존합계+(수열값x현재 숫자)를 계산해서 넘겨줌
- 인덱스에 도달했고 합계가 같을때는 result 값에 순서대로 결과배열에 담아둔 수를 더해줌
- 솔루션 메서드에서는 만약 결과 배열이 채워졌다면 그 뒤는 굳이 체크할 필요가 없으니 return 처리.

IM

DFS, BFS 기출문제 풀이

수열 추측하기