Dev.baelanche

81칸 중에 비어있는 칸이 있다면 백트래킹으로 하나하나 채워간다. 수를 채울 때 가로줄, 세로줄, 3x3칸에 중복되는 수가 없게한다. public static boolean inputNumber(int r, int c, int num) { for(int i=0; i

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..