[문제풀이] 08-08. 수열 추측하기

인프런, 자바(Java) 알고리즘 문제풀이

DFS, BFS 활용 - 0808. 수열 추측하기(DFS)

---

🗒️ 문제

---

🎈 나의 풀이

	private static int n, m, C[][], nums[], coms[], answer[];

    private static int combination(int n, int r) {
        if(n == r || r == 0) return 1;
        if(r == 1) return n;
        if(C[n][r] == 0) C[n][r] = combination(n-1, r-1) + combination(n-1 , r);
        return C[n][r];
    }
    private static boolean DFS(int L) {
        if (L == n) {
            int sum = 0;
            for(int i=0; i<n; i++) sum += coms[i] * answer[i];
            if(sum == m) return true;
        } else {
            for (int i = 0; i < nums.length; i++) {
                if (nums[i] == 0) {
                    answer[L] = i + 1;
                    nums[i] = 1;
                    if(DFS(L+1)) return true;
                    nums[i] = 0;
                }
            }
        }
        return false;
    }
    private static void solution() {
        nums = new int[n];
        coms = new int[n];
        answer = new int[n];

        for(int i=0; i<=n-1; i++) {
            coms[i] = combination(n-1, i);
        }
        DFS(0);
    }
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        m = sc.nextInt();
        C = new int[n+1][n+1];
        solution();

        for(int i : answer) System.out.print(i + " ");
    }

---

🖍️ 강의 풀이

  	static int[] b, p, ch;
	static int n, f;
	boolean flag=false;
	int[][] dy=new int[35][35];
	public int combi(int n, int r){
		if(dy[n][r]>0) return dy[n][r];
		if(n==r || r==0) return 1;
		else return dy[n][r]=combi(n-1, r-1)+combi(n-1, r);
	}

	public void DFS(int L, int sum){
		if(flag) return;
		if(L==n){
			if(sum==f){
				for(int x : p) System.out.print(x+" ");
				flag=true;
			}
		}
		else{
			for(int i=1; i<=n; i++){
				if(ch[i]==0){
					ch[i]=1;
					p[L]=i;
					DFS(L+1, sum+(p[L]*b[L]));
					ch[i]=0;
				}
			}
		}
	}

	public static void main(String[] args){
		Main T = new Main();
		Scanner kb = new Scanner(System.in);
		n=kb.nextInt();
		f=kb.nextInt();
		b=new int[n];
		p=new int[n];
		ch=new int[n+1];
		for(int i=0; i<n; i++){
			b[i]=T.combi(n-1, i);
		}
		T.DFS(0, 0);
	}

---

💬 짚어가기

해당 문제는 DFS를 이용하여 풀 수 있다. 우선 문제의 규칙을 살펴보자.

n번 째 줄의 수열 추측하기 : 규칙

1. n번 째 줄(가장 윗줄)에는 1부터 n까지, n개의 수가 등장한다.
2. n번 째 수열과 { $_{n-1}C_{0}$ $...$ $_{n-1}C_{n-1}$ }을 차례로 곱한 값이 삼각형의 가장 아래 값이 같다.

문제에 제시된 이미지의 예로 4번 째 줄에 등장하는 수열 { 3, 1, 2, 4 }와 { $_{3}C_{0}$ $...$ $_{3}C_{3}$ }을
차례로 곱한 값을 살펴보면, 3 $*$ $_{3}C_{0}$ $+$ 1 $*$ $_{3}C_{1}$ $+$ 2 $*$ $_{3}C_{2}$ $+$ 4 $*$ $_{3}C_{3}$ $=$ $16$ 이다.

따라서 해당 문제를 풀기 위해서는 n번 째 줄에 등장하는 조합 { $_{n-1}C_{0}$ $...$ $_{n-1}C_{n-1}$ }을 구하고,
1부터 n까지 수열을 나열하는 경우의 수를 순회하며, 서로 곱한 값을 확인한다.

나의 풀이에서는 coms 배열에 조합의 결과를 보관하도록 하고, nums 배열을 이용하여 인덱스에
해당하는 숫자의 사용 여부를 구분하도록 했다. 이후 DFS를 수행하며 answer 배열에 나열할 수
있는 경우의 수를 보관하였다.

모든 수가 나열됐을 때 answer와 coms 배열의 곱을 확인하여 정답을 반환하도록 구현했다.
강의 또한 동일한 로직으로 구성됐다.