Dev.baelanche

N*N의 체스판에 N개의 퀸을 놓는 경우를 모두 체크해야 한다. N개의 퀸을 모두 움직여봐야 하므로 백트래킹을 사용한다. 백트래킹은 설명이 좀 난해하여 로직을 서술하겠다. 퀸은 가로, 세로, 대각선으로 움직이는 말이라는 것을 사전에 알아야 한다. 코드 1 public class Main { static int n; static int a[][]; static int cnt = 0; public static void main(String[] args) throws Exception { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); n = Integer.parseInt(br.readLine()); a = new int[n+..

보드에서 모든 경우를 탐색해야 하기 때문에 백트래킹을 활용한다. static boolean alpha[] = new boolean[26]; static boolean visited[][]; static int dr[] = {-1, 1, 0, 0}; static int dc[] = {0, 0, -1, 1}; 1. 알파벳은 최대 1번만 사용 가능하기 때문에 배열을 만들어 각 알파벳 별로 사용했는지 여부를 체크한다. 2. DFS 도중 같은 지점은 방문할 수 없으므로 방문기록 배열을 만든다. 3. 상하좌우로 이동하기 때문에 방향배열을 만든다. if(!visited[nr][nc] && !alpha[a[nr][nc] - 'A']) { visited[nr][nc] = true; alpha[a[nr][nc] - 'A'..

DFS로 완전탐색하여 조건에 맞는 암호를 모두 찾아내면 된다. 1. 사전식으로 출력해야 하므로 입력받은 배열은 오름차순으로 정렬한다. 2. 재귀 + 반복문으로 진행하며 현재의 문자보다 큰 문자가 나오면 문자를 카운트했을때와 안했을때로 분기한다. 3. 문자를 카운트 할때마다 자음인지 모음인지 체크한다. 4. l 과 문자의 길이가 같고 자음, 모음의 조건을 만족하면 출력한다. public class Main { static int l; static int c; static char a[]; public static void main(String[] args) { Scanner sc = new Scanner(System.in); l = sc.nextInt(); c = sc.nextInt(); a = new c..

숫자 사이사이에 들어갈 기호를 모두 대입해보며 진행해야 한다. 일반적인 완전탐색으로는 구현하기 힘들고 재귀를 이용한 탐색을 사용해야 한다. 백트래킹 기법을 이용하여 앞서 대입한 연산자도 바꿀수 있게했다. public class Main { static int n; static int a[]; static int oper[]; static int max = Integer.MIN_VALUE; static int min = Integer.MAX_VALUE; public static void main(String[] args) { Scanner sc = new Scanner(System.in); n = sc.nextInt(); a = new int[n]; oper = new int[4]; for(int i=0;..

문제에 나와있는 규칙을 잘 지키며 BFS를 수행해야 한다. 주의할 점은 따로 없어 코드에 주석을 달아놓았다. public class Main { static int n; static int m; static int a[][]; public static void main(String[] args) { Scanner sc = new Scanner(System.in); n = sc.nextInt(); m = sc.nextInt(); a = new int[n][m]; int r = sc.nextInt(); int c = sc.nextInt(); int d = sc.nextInt(); for(int i=0; i

N일 마다 벌 수 있는 최대 이익을 저장하면서 진행한다. dp[i] = a[i][1]; //상담 이익 dp배열의 초기값은 상담 이익으로 했다. 예제의 예를 들면 1일 2일 3일 4일 5일 6일 7일 Ti 3 5 1 1 2 4 2 Pi 10 20 10 20 15 40 200 Pi 의 값을 모두 넣어준 셈인데 6일, 7일에 주어진 일은 완료할 수가 없다. 이에 대한 예외처리는 마지막에 해주었다. 1일부터 진행하며 그 날 주어진 상담을 완료할 수 있으면 dp 값을 올려준다. n번째날의 일을 수행하여 n+1번째날의 일을 수행하지 못하면 손해가 될 수 있으므로 dp값을 업데이트 할때는 기존의 값과 비교하여 큰 값으로 갱신해주어야 한다. if(i - j >= a[j][0]) dp[i] = max(dp[j] + a[..

n 배열을 오름차순으로 정렬하고 이분탐색으로 구현했다. 1. low, high는 각각 n배열의 최솟값, 최댓값으로 정했다. 2. mid 위치의 값과 현재 선택한 m 배열의 값을 비교하여 low, high 를 바꿔준다. public class Main { public static void main(String[] args) throws Exception { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out)); StringTokenizer st = new StringTokenizer(br.read..

최소 회수를 출력하라길래 BFS로 풀었다. 1. 4자리수의 소수 배열을 저장해 놓는다. 2. 매 탐색시 각 자리수를 0~9로 바꾸며 소수인지 아닌지 체크하며 소수이면 큐에 담는다. 3. 만들어진 수와 입력받은 수가 같으면 정지한다. 4자리수가 안되는 수는 모두 소수가 아니라고 저장하여 예외처리했다. 그리고 따로 방문이력을 담은 배열을 만들어 체크해 주어야 불가능한 경우를 알아낼 수 있다. public class Main { static boolean prime[] = new boolean[10000]; public static void main(String[] args) throws Exception { BufferedReader br = new BufferedReader(new InputStreamRe..