백준
백준 닷컴 단계 별로 풀어보기 22단계
CD가참둥그렇다
2023. 10. 27. 12:34
1단계 N과 M (1) (백준 15649)
- 1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열
- 첫째 줄에 자연수 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 8)
- 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다.
- 수열은 사전 순으로 증가하는 순서로 출력해야 한다.
import java.io.*;
import java.util.*;
public class Step_1 {
static int n;
static int m;
static int[] arr;
static boolean[] check;
static StringBuilder sb = new StringBuilder();
public static void main(String[] args) throws IOException {
Scanner sc = new Scanner(System.in);
n = sc.nextInt();
m=sc.nextInt();
arr = new int[m];
check = new boolean[n];
find(0);
System.out.println(sb.toString());
}
public static void find(int index) {
if(index==m) {
for(int i=0; i<m; i++) {
if(i!=m-1) {
sb.append(arr[i]+1+" ");
} else {
sb.append(arr[i]+1+"\\n");
}
}
} else {
for(int i=0; i<n; i++) {
if(check[i]) {
continue;
} else {
check[i] = true;
arr[index] = i;
find(index+1);
}
check[i]=false;
}
}
}
}
A.
- 백트래킹은 반복문을 돌릴 때 필요 없는 반복문을 실행하지 않고 스킵하여 반복회수를 줄이는 기법이다.
- 이미 선택한 숫자는 boolean 값을 true로 바꿔 중복 등장 시 반복문을 실행하지 않도록 해준다.
2단계 N과 M (2) (백준 15650)
- 1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열
- 고른 수열은 오름차순이어야 한다.
- 첫째 줄에 자연수 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 8)
- 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다.
- 수열은 사전 순으로 증가하는 순서로 출력해야 한다.
import java.io.*;
import java.util.*;
public class Step_1 {
static int n;
static int m;
static int[] arr;
static boolean[] check;
static StringBuilder sb = new StringBuilder();
public static void main(String[] args) throws IOException {
Scanner sc = new Scanner(System.in);
n = sc.nextInt();
m=sc.nextInt();
arr = new int[m];
check = new boolean[n];
find(0);
System.out.println(sb.toString());
}
public static void find(int index) {
if(index==m) {
for(int i=0; i<m; i++) {
if(i!=m-1) {
sb.append(arr[i]+1+" ");
} else {
sb.append(arr[i]+1+"\\n");
}
}
} else {
for(int i=0; i<n; i++) {
if(check[i]) {
continue;
} else {
check[i] = true;
arr[index] = i;
find(index+1);
}
check[i]=false;
}
}
}
}
A.
- 순서도 맞추는 중복되지 않는 숫자의 조합은 반복문의 범위를 지정하면 쉽게 만들 수 있다.
- 5 2인 경우 1~4까지의 숫자를 고르고 그 숫자+1부터 5까지를 반복하도록 하면 된다.
- 10 4인 경우 1~7까지 숫자를 고르고 고른 숫자 +1부터 8까지, 그리고 다음 고른 숫자 +1 부터 9까지, 그리고 다음 고른 숫자 +1부터 10까지 반복문이 실시되도록 재귀함수를 만들어준다.
3단계 N과 M (3) (백준 15651)
- 1부터 N까지 자연수 중에서 M개를 고른 수열
- 같은 수를 여러 번 골라도 된다.
- 첫째 줄에 자연수 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 7)
- 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다.
- 수열은 사전 순으로 증가하는 순서로 출력해야 한다.
import java.io.*;
import java.util.*;
public class Step_3 {
static int n;
static int m;
static int[] arr;
static StringBuilder sb = new StringBuilder();
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
n = sc.nextInt();
m = sc.nextInt();
arr = new int[m];
pick(0);
System.out.println(sb.toString());
}
public static void pick(int idx) {
if (idx == m) {
for (int i = 0; i < m; i++) {
if (i != m - 1) {
sb.append(arr[i] + " ");
} else {
sb.append(arr[i] + "\\n");
}
}
} else {
for (int i = 0; i < n ; i++) {
arr[idx] = i + 1;
pick(idx + 1);
}
}
}
}
A.
- 가장 기초적인 재귀 함수를 사용한 반복문을 작성하면 된다.
4단계 N과 M (4) (백준 15652)
- 1부터 N까지 자연수 중에서 M개를 고른 수열
- 같은 수를 여러 번 골라도 된다.
- 고른 수열은 비내림차순이어야 한다
- 길이가 K인 수열 A가 A1 ≤ A2 ≤ ... ≤ AK-1 ≤ AK를 만족하면, 비내림차순이라고 한다.
- 첫째 줄에 자연수 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 8)
- 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다.
- 수열은 사전 순으로 증가하는 순서로 출력해야 한다.
import java.io.*;
import java.util.*;
public class Step_4 {
static int n;
static int m;
static int[] arr;
static StringBuilder sb = new StringBuilder();
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
n = sc.nextInt();
m = sc.nextInt();
arr = new int[m];
pick(0, 0);
System.out.println(sb.toString());
}
public static void pick(int idx, int start) {
if (idx == m) {
for (int i = 0; i < m; i++) {
if (i != m - 1) {
sb.append(arr[i] + " ");
} else {
sb.append(arr[i] + "\\n");
}
}
} else {
for (int i = start; i < n; i++) {
arr[idx] = i + 1;
pick(idx + 1, i);
}
}
}
}
A.
- 2단계의 구조를 베이스로 하고, 반복문의 마지막은 n, 재귀하는 함수의 start에 들어가는 수에 +1을 제외하고 i를 넣어주면 비 내림차순으로 만들 수 있다.
5단계 N-Queen (백준 9663)
- N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다.
- N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오.
- 첫째 줄에 N이 주어진다. (1 ≤ N < 15)
- 첫째 줄에 자연수 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 8)
import java.io.*;
import java.util.*;
public class Step_5 {
static int n;
static int result = 0;
static int[] chess;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
n = sc.nextInt();
chess = new int[n];
queen(0);
System.out.println(result);
}
public static void queen(int idx) {
if (idx == n) {
result++;
} else {
check: for (int i = 0; i < n; i++) {
for (int j = 0; j < idx; j++) {
if (chess[j] == i) { // 하단 줄
continue check;
}
if (chess[j] + j == i + idx) {// 좌하단 대각선
continue check;
}
if (chess[j] - j == i - idx) {// 우하단 대각선
continue check;
}
}
chess[idx] = i;
queen(idx + 1);
}
}
}
}
A.
- 퀸은 가로세로 대각선 공격이 가능하기 때문에 각 줄에 퀸을 하나씩 놓아야 하기 때문에 1차원 int 배열 chess를 크기 n으로 만들어 줄 수 있다.
- 0~n-1까지의 반복문을 만들고 각 반복문에 이전까지 퀸의 공격 경로에 있는지 체크한다.
- chess에 이미 있는 값이면 continue, 좌하단 대각선은 chess의 숫자와 idx가 동일한 경우이니 continue, 우하단 대각선은 각 idx 값과 chess의 배열 내부 값이 같은 것이기 때문에 continue를 해 주도록 한다.
- queen 메소드의 idx가 n에 정상 도달한 경우 result를 1 증가시키도록 한다.
6단계 스도쿠 (백준 2580)
- 아홉 줄에 걸쳐 한 줄에 9개씩 게임 시작 전 스도쿠판 각 줄에 쓰여 있는 숫자가 한 칸씩 띄워서 차례로 주어진다. 스도쿠 판의 빈 칸의 경우에는 0이 주어진다. 스도쿠 판을 규칙대로 채울 수 없는 경우의 입력은 주어지지 않는다.
- 모든 빈 칸이 채워진 스도쿠 판의 최종 모습을 아홉 줄에 걸쳐 한 줄에 9개씩 한 칸씩 띄워서 출력한다.
- 스도쿠 판을 채우는 방법이 여럿인 경우는 그 중 하나만을 출력한다.
package stage22;
import java.io.*;
import java.util.*;
public class Step_6 {
static int[][] sudoku = new int[9][9];
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
for (int i = 0; i < 9; i++) {
st = new StringTokenizer(br.readLine());
for (int j = 0; j < 9; j++) {
sudoku[i][j] = Integer.parseInt(st.nextToken());
}
}
sudoku(0, 0);
}
public static void sudoku(int a, int b) {
if(b==9) {
sudoku(a+1, 0);
return;
}
if(a==9) {
show();
System.exit(0);
}
if(sudoku[a][b]==0) {
for(int i=1; i<=9; i++) {
if(check(i, a, b)) {
sudoku[a][b] = i;
sudoku(a, b+1);
}
}
sudoku[a][b]=0;
return;
}
sudoku(a, b+1);
}
public static boolean check(int num, int a, int b) {
for(int i = 0; i<9; i++) {
if(sudoku[a][i]==num) {
return false;
}
}
for(int i = 0; i<9; i++) {
if(sudoku[i][b]==num) {
return false;
}
}
int tempA = a/3;
int tempB = b/3;
for(int i=tempA*3; i<tempA*3+3; i++) {
for(int j=tempB*3; j<tempB*3+3; j++) {
if(sudoku[i][j]==num) {
return false;
}
}
}
return true;
}
public static void show() {
StringBuilder sb = new StringBuilder();
for (int i = 0; i < 9; i++) {
for (int j = 0; j < 9; j++) {
if (j == 8) {
sb.append(sudoku[i][j] + "\\n");
} else {
sb.append(sudoku[i][j] + " ");
}
}
}
System.out.println(sb.toString());
}
}
A.
- 무작위로 대입해서 결과를 보아야 하는 재귀함수의 경우 가능한 수를 대입하여 다음 재귀함수를 호출하고 재귀함수 진행 도중 문제가 발생하여 돌아오는 방법으로 재귀함수 다음 return을 써주면 된다.
- 재귀함수 다음에 return을 할 경우 모든 대입의 경우의 수를 체크하며 가능한 경우 결과가 오게 된다.
- 스도쿠를 int 배열에 담아준다.
- 스도쿠 메소드를 만들고 행열의 값을 int로 받도록 한다.
- 행열에 맞는 배열의 값이 0인 경우 대입을 진행한다.
- 1~9까지의 대입을 하며 스도쿠 조건에 맞는 대입인 경우 다음 번호를 지정하여 재귀함수가 진행된다.
- 재귀함수의 진행 중 마지막 번호까지의 진행을 마친 경우 출력을 한다. 진행되지 않은 경우 return을 통해 돌아간 다음, 다음 번호의 대입을 진행하게 된다.
7단계 연산자 끼워넣기 (백준 14888)
- 식의 계산은 연산자 우선 순위를 무시하고 앞에서부터 진행해야 한다. 또, 나눗셈은 정수 나눗셈으로 몫만 취한다. 음수를 양수로 나눌 때는 C++14의 기준을 따른다. 즉, 양수로 바꾼 뒤 몫을 취하고, 그 몫을 음수로 바꾼 것과 같다. 이에 따라서, 위의 식 4개의 결과를 계산해보면 아래와 같다.
- 첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다. 둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 100) 셋째 줄에는 합이 N-1인 4개의 정수가 주어지는데, 차례대로 덧셈(+)의 개수, 뺄셈(-)의 개수, 곱셈(×)의 개수, 나눗셈(÷)의 개수이다.
- 첫째 줄에 만들 수 있는 식의 결과의 최댓값을, 둘째 줄에는 최솟값을 출력한다. 연산자를 어떻게 끼워넣어도 항상 -10억보다 크거나 같고, 10억보다 작거나 같은 결과가 나오는 입력만 주어진다. 또한, 앞에서부터 계산했을 때, 중간에 계산되는 식의 결과도 항상 -10억보다 크거나 같고, 10억보다 작거나 같다.
import java.io.*;
import java.util.*;
public class Step_7 {
static int[] arr;
static int[] arrCalc;
static int[] calc = new int[4];
static int max;
static int min;
static int temp;
static boolean First;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
arr = new int[Integer.parseInt(br.readLine())];
arrCalc = new int[arr.length-1];
st = new StringTokenizer(br.readLine());
for(int i=0; i<arr.length; i++) {
arr[i] = Integer.parseInt(st.nextToken());
}
st = new StringTokenizer(br.readLine());
for(int i=0; i<4; i++) {
calc[i] = Integer.parseInt(st.nextToken());
}
find(0);
System.out.println(max);
System.out.println(min);
}
public static void find(int idx) {
if(idx == arr.length-1) {
temp = arr[0];
for(int i=0; i<arrCalc.length; i++) {
temp = calc(temp, arr[i+1], arrCalc[i]);
}
if(!First) {
max = temp;
min = temp;
First = true;
} else if(temp>max) {
max = temp;
} else if(temp<min) {
min = temp;
}
}
for(int i=0; i<4; i++) {
if(calc[i]==0) {
continue;
}
calc[i]--;
arrCalc[idx] = i;
find(idx+1);
calc[i]++;
}
}
public static int calc(int a, int b, int type) {
switch (type) {
case 0:
return a+b;
case 1:
return a-b;
case 2:
return a*b;
case 3:
return a/b;
default:
return 0;
}
}
}
A.
- 재귀함수를 이용하여 가능한 모든 연산자 조합을 만든다. 각 연산자 개수의 제한이 있기 때문에 다음 재귀함수를 만들기 전에 해당 연산자의 개수를 1 줄이고, 재귀함수에서 돌아올 때 해당 연산자의 개수를 1 늘리는 방식으로 체크할 수 있다.
- 연산자의 남은 개수가 0개인 경우는 무시하여 빠르게 돌릴 수 있다.
8단계 스타트와 링크 (백준 14889)
- 첫째 줄에 N(4 ≤ N ≤ 20, N은 짝수)이 주어진다. 둘째 줄부터 N개의 줄에 S가 주어진다. 각 줄은 N개의 수로 이루어져 있고, i번 줄의 j번째 수는 Sij 이다. Sii는 항상 0이고, 나머지 Sij는 1보다 크거나 같고, 100보다 작거나 같은 정수이다.
- 첫째 줄에 스타트 팀과 링크 팀의 능력치의 차이의 최솟값을 출력한다.
import java.io.*;
import java.util.*;
public class Step_8 {
static int[][] statBonus;
static int[] team1;
static int[] team2;
static int gap;
static int temp;
static int teamCap1;
static int teamCap2;
static boolean first = true;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
int n = Integer.parseInt(br.readLine());
statBonus = new int[n][n];
team1 = new int[n / 2];
team2 = new int[n / 2];
teamCap1 = n / 2;
teamCap2 = n / 2;
for (int i = 0; i < n; i++) {
st = new StringTokenizer(br.readLine());
for (int j = 0; j < n; j++) {
statBonus[i][j] = Integer.parseInt(st.nextToken());
}
}
splitTeam(0);
System.out.println(gap);
}
public static void splitTeam(int idx) {
if (idx == statBonus.length) {
sumBonus();
return;
}
if (teamCap1 != 0) {
team1[team1.length - teamCap1] = idx;
teamCap1--;
splitTeam(idx + 1);
teamCap1++;
}
if (teamCap2 != 0) {
team2[team2.length - teamCap2] = idx;
teamCap2--;
splitTeam(idx + 1);
teamCap2++;
}
}
public static void sumBonus() {
temp = 0;
for (int i = 0; i < team1.length; i++) {
for (int j = 0; j < team1.length; j++) {
temp += statBonus[team1[i]][team1[j]];
}
}
for (int i = 0; i < team2.length; i++) {
for (int j = 0; j < team2.length; j++) {
temp -= statBonus[team2[i]][team2[j]];
}
}
temp = Math.abs(temp);
if (first) {
gap = temp;
first = false;
} else if (gap > temp) {
gap = temp;
}
}
}
A.
- 재귀함수를 통해 팀을 나누어 각각 배열에 담아준다. 팀 최대치를 넘어가는 경우 스킵되도록 한다.
- 팀이 나누어질 때 마다 팀 보너스 차이를 계산하여준다. 첫 차이는 gap에 직접 넣어주고, 그 이후는 gap과 비교하여 가장 작은 값을 남기도록 한다.
- gap을 출력한다.