Java : 수열 추측하기

문제

풀이

• 수열 문제
• n개 중에 n개를 뽑는 수열을 사용하여 1,2,3,4 ~ 4,3,2,1 까지 돌려보면서 f(16)이 나올 때 까지 dfs 돌린다.
• 처음에 수열인지 모르고 도대체 어떻게 풀어야 하나 했는데 문득 순열 조합이 생각나면서 순열 구현 방법부터 공부하고 다시 풀어보니 풀렸다.

전체 코드

package inflearn;

import java.util.Arrays;
import java.util.Scanner;

public class I0808 {
  static int n, f;
  static boolean flag = false;
  static int[] arr;
  static boolean[] visited;
  static int[] output;

  public static void main(String[] args) {

    Scanner sc = new Scanner(System.in);
    n = sc.nextInt();
    f = sc.nextInt();

    arr = new int[n];
    visited = new boolean[n];
    output = new int[n];
    for (int i = 0; i < n; i++) {
      arr[i] = i + 1;
      visited[i] = false;
    }
    int depth = 0;

    dfs(depth, n, n);
    for (int i = 0; i < n; i++) {
      System.out.print(output[i] + " ");
    }
  }

  static void dfs(int depth, int n, int r) {
    if (depth == r) {
      if (isAnswer(output)) flag = true;
      return;
    }

    for (int i = 0; i < n; i++) {
      if (flag) return;
      if (!visited[i]) {
        visited[i] = true;
        output[depth] = arr[i];
        dfs(depth + 1, n, r);
        visited[i] = false;
      }
    }

  }

  static boolean isAnswer(int[] tmp) {

    int[] ch = tmp.clone();
    for (int j = ch.length - 1; j > 0; j--) {
      for (int i = 0; i < j; i++) {
        ch[i] = ch[i] + ch[i + 1];
      }
    }
    return ch[0] == f;
  }

}