📙 Algorithm Solving/Java
📙[Algo] 24.02.19 알고리즘
혜덕hyeduck
2024. 2. 20. 00:43
알고리즘 문제) BOJ 1182. 부분수열의 합
문제 요약
- N개의 정수로 이루어진 수열이 있을 때, 크기가 양수인 부분수열 중에서 그 수열의 원소를 다 더한 값이 S가 되는 경우의 수
시간 제한
- 2초
입력
- N S
- 1≤N≤20
- S : -100만~100만
- N개의 정수
- 정수의 절댓값은 10만을 넘지 않음
출력
- 합이 S가 되는 부분수열개수 구하
접근법
- 1개~N개를 고르는 모든 경우의 수를 찾는 문제!
- depth가 1~N으로 달라지기 때문에 백트랙킹으로 풀어야 하는 문제였다.
코드
import java.io.*;
import java.util.StringTokenizer;
public class Main {
static int N, S;
static int[] arr;
static int[] selected;
static int size, cnt;
static void recur(int cur, int start) {
if (cur == size) {
int sum = 0;
for (int i = 0; i < N; i++) {
sum += arr[selected[i]];
}
if (sum == S) {
cnt++;
}
return;
}
for (int i = start; i <= N; i++) {
selected[cur] = i;
recur(cur + 1, i + 1);
}
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringTokenizer st;
st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
S = Integer.parseInt(st.nextToken());
st = new StringTokenizer(br.readLine());
arr = new int[N + 1];
for (int i = 1; i <= N; i++) {
arr[i] = Integer.parseInt(st.nextToken());
}
selected = new int[N];
for (int i = 1; i <= N; i++) {
// 크기가 1~N개인 경우
size = i;
recur(0, 1);
}
bw.write(String.valueOf(cnt));
bw.flush();
bw.close();
br.close();
}
}
알고리즘 문제) BOJ 16938. 캠프 준비
문제 요약
- N개의 문제들이 각각 난이도를 수치로 갖고 있음
- Ai
- 캠프에 사용할 문제는
- 두 문제 이상이어야 하고,
- 난이도의 합은 L보다 크거나 같고, R보다 작거나 같을 것
- 가장 어려운 문제와 가장 쉬운 문제 난이도 차이는 X보다 크거나 같을 것
시간 제한
- 2초
입력
- N L R X
- 1≤N≤15
- 1≤L≤R≤10억
- 1≤X≤100만
- 1≤Ai≤100만
- A1, .. A2, … AN
출력
- 문제를 고르는 방법의 수 구하기
접근법
- 완전 탐색으로 접근하기
- 2~N개를 고를 때 케이스를 나눠야 한다.
- 고르는 문제 수마다 for문의 중첩 개수가 달라지므로 백트랙킹으로 접근해야한다.
- 백트랙킹 가지치기
- 첫 번째 조건 : L ≤ sum(난이도 합) ≤ R
- 이거를 하나씩 원소를 채워갈 때 R을 초과하는 경우를 미리 필터링하며 가지치기하고,
- 모두 채웠을 때 L보다 크거나 같은지 한번 더 체크할 것
- 합계는 하나씩 채워간다.
- 두 번째 조건 : 최대 난이도 - 최소 난이도 ≥ X
- 첫 번째 조건을 통과할때 두 번째 조건도 체크할 것
- 첫 번째 조건 : L ≤ sum(난이도 합) ≤ R
코드
import java.io.*;
import java.util.StringTokenizer;
public class Main {
static int N, L, R, X;
static int[] arr;
static int size;
static int[] selected;
static int answer;
static void recur(int cur, int start, int sum) {
if (sum > R) return;
if (cur == size) {
if (sum < L) return;
int max = 1, min = 1000000;
for (int i = 0; i < size; i++) {
if(max < arr[selected[i]]) max = arr[selected[i]];
if(min > arr[selected[i]]) min = arr[selected[i]];
}
if(max - min < X) return;
answer++;
return;
}
for (int i = start; i <= N; i++) {
selected[cur] = i;
sum += arr[selected[cur]];
recur(cur + 1, i + 1, sum);
sum -= arr[selected[cur]];
}
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringTokenizer st;
st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken()); // 문제 개수
L = Integer.parseInt(st.nextToken()); // 문제 난이도 합 제한 최솟값
R = Integer.parseInt(st.nextToken()); // 문제 난이도 합 제한 최댓값
X = Integer.parseInt(st.nextToken()); // 문제 난이도 최대-최소 기준
st = new StringTokenizer(br.readLine());
arr = new int[N + 1]; // 문제 난이도
for (int i = 1; i <= N; i++) {
arr[i] = Integer.parseInt(st.nextToken());
}
selected = new int[N];
for (int i = 2; i <= N; i++) {
size = i;
recur(0, 1, 0);
}
bw.write(String.valueOf(answer));
bw.flush();
bw.close();
br.close();
}
}
알고리즘 문제) BOJ 10819. 차이를 최대로
문제 요약
- N개의 정수로 이루어진 배열 A
- 배열 정수의 순서를 적절히 바꿔서 다음 식의 최댓값 구하는 프로그램 작성
- abs(A[0]-A[1]) + … + abs(A[N-2]-A[N-1])
시간 제한
- 1초
입력
- N
- 3 ≤ N ≤ 8
- 배열 A의 정수
- -100~100
출력
- 배열의 순서를 적절히 바꿔 얻을 수 있는 식의 최댓값?
접근법
- 완전 탐색으로 접근하기
- N개의 정수를 중복 없이 N개를 뽑는 순열을 구해야함.
- for문 개수가 N의 입력값에 따라 달라지므로 백트랙킹으로 풀 것.
- 조건 체크
- N개를 모두 뽑고나서 식의 결과값을 구하고 최댓값 갱신
코드
import java.io.*;
import java.util.StringTokenizer;
public class Main {
static int N; // 배열 크기
static int[] arr; // 배열
static int answer;
static boolean[] visited;
static int[] selected;
static void recur(int cur) {
if (cur == N) {
int sum = 0;
for (int i = 0; i < N - 1; i++) {
sum += Math.abs(selected[i] - selected[i + 1]);
}
answer = Math.max(answer, sum);
return;
}
for (int i = 0; i < N; i++) {
if(visited[i]) continue;
visited[i] = true;
selected[cur] = arr[i];
recur(cur + 1);
visited[i] = false;
}
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringTokenizer st;
N = Integer.parseInt(br.readLine());
st = new StringTokenizer(br.readLine());
arr = new int[N];
for (int i = 0; i < N; i++) {
arr[i] = Integer.parseInt(st.nextToken());
}
visited = new boolean[N];
selected = new int[N];
recur(0);
bw.write(String.valueOf(answer));
bw.flush();
bw.close();
br.close();
}
}
알고리즘 문제) BOJ 20950. 미술가 미미
문제 요약
- RGB 표기하기
- 혼합할 모든 물건의 R값끼리 더하고 개수로 나눈다.
- G. B도 똑같이 구함
- 곰두리색의 RGB가 구해졌을 때 RGB 차이가 가장 적은 차이값 출력하기
- 차이값 : abs(Ri-Rj) + abs(Gi-Gj) + abs(Bi-Bj)
- 단, 최대 7개까지만 섞을 수 있고, 1개만으로 사할수도 없음
시간 제한
- 1초
입력
- 물감 개수 N
- 2≤N≤30
- N개의 줄에 물감의 RGB 값
- 곰두리색의 RGB
- 0≤R,G,B≤255
출력
- 곰두리색과 RGB차이가 가장 적은 값 차이값 출력
접근법
- 2~7개 색을 고르는 모든 경우의 수를 구하고, 그때 혼합 RGB값을 구한 뒤 곰두리색과의 차이값 구함 ⇒ 최솟값 갱신
코드
import java.io.*;
import java.util.StringTokenizer;
public class Main {
static int N;
static int[][] colors;
static int[] gomduri;
static int size;
static int[] selected;
static int answer = Integer.MAX_VALUE;
static void recur(int cur, int start) {
if (cur == size) {
int R = 0, G = 0, B = 0;
for (int i = 0; i < size; i++) {
R += colors[selected[i]][0];
G += colors[selected[i]][1];
B += colors[selected[i]][2];
}
answer = Math.min(answer, Math.abs(gomduri[0] - R / size)
+ Math.abs(gomduri[1] - G / size) + Math.abs(gomduri[2] - B / size));
return;
}
for (int i = start; i < N; i++) {
selected[cur] = i;
recur(cur + 1, i + 1);
}
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringTokenizer st;
N = Integer.parseInt(br.readLine());
colors = new int[N][3];
for (int i = 0; i < N; i++) {
st = new StringTokenizer(br.readLine());
colors[i][0] = Integer.parseInt(st.nextToken());
colors[i][1] = Integer.parseInt(st.nextToken());
colors[i][2] = Integer.parseInt(st.nextToken());
}
gomduri = new int[3];
st = new StringTokenizer(br.readLine());
gomduri[0] = Integer.parseInt(st.nextToken());
gomduri[1] = Integer.parseInt(st.nextToken());
gomduri[2] = Integer.parseInt(st.nextToken());
selected = new int[N];
for (int i = 2; i <= 7; i++) {
if(i > N) break;
size = i;
recur(0, 0);
}
bw.write(String.valueOf(answer));
bw.flush();
bw.close();
br.close();
}
}
알고리즘 문제) BOJ 15686. 치킨 배달
문제 요약
- 크기 N*N
- 치킨 거리 : 집에서 가장 가까운 치킨집과의 거리
- 도시의 치킨 거리 : 모든 집의 치킨 거리의 합
- 거리 = abs(r1-r2) + abs(c1-c2)
- 1: 집, 2: 치킨집
- 치킨집 중 M개를 제외한 나머지는 폐업 시킴 ⇒ 이때 도시의 치킨 거리가 가장 적은 경우 찾기
시간 제한
- 1초
입력
- N, M
- 2≤N≤50
- 1≤M≤13
- 도시 정보
- 0 빈칸, 1 집, 2 치킨집
- 집의 개수는 2N개를 넘지 않음
- M≤치킨집 개수≤13
출력
- 치킨집을 최대 M개 골랐을 때, 도시의 치킨 거리 최솟값 구하기
접근법
- 치킨집 중 M개를 고르는 모든 경우의 수를 구하고, 이때 치킨거리를 구하며 최솟값 갱신
- 13C7인경우가 가장 큰 경우의 수로 1716가지가 나옴
- 50*1716정도 걸리므로 완탐으로 돌려도 가능
코드
import java.io.*;
import java.util.ArrayList;
import java.util.StringTokenizer;
public class Main {
static int N, M;
static ArrayList<Point> chickens = new ArrayList<>();
static ArrayList<Point> houses = new ArrayList<>();
static int chickenCnt, houseCnt;
static int[] selected;
static int answer = Integer.MAX_VALUE;
static class Point {
int row;
int col;
Point(int row, int col) {
this.row = row;
this.col = col;
}
}
static void recur(int cur, int start) {
if (cur == M) {
int sum = 0, dist, hr, hc, kr, kc;
for (int i = 0; i < houseCnt; i++) {
dist = 1000;
hr = houses.get(i).row;
hc = houses.get(i).col;
for (int j = 0; j < M; j++) {
kr = chickens.get(selected[j]).row;
kc = chickens.get(selected[j]).col;
dist = Math.min(dist, Math.abs(hr - kr) + Math.abs(hc - kc));
}
sum += dist;
}
answer = Math.min(answer, sum);
return;
}
for (int i = start; i < chickenCnt; i++) {
selected[cur] = i;
recur(cur + 1, i + 1);
}
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringTokenizer st;
st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
for (int i = 0; i < N; i++) {
st = new StringTokenizer(br.readLine());
int input;
for (int j = 0; j < N; j++) {
input = Integer.parseInt(st.nextToken());
if (input == 2) {
chickens.add(new Point(i, j));
} else if (input == 1) {
houses.add(new Point(i, j));
}
}
}
chickenCnt = chickens.size();
houseCnt = houses.size();
selected = new int[M];
recur(0, 0);
bw.write(String.valueOf(answer));
bw.flush();
bw.close();
br.close();
}
}
알고리즘 문제) BOJ 16943. 숫자 재배치
문제 요약
- 두 정수 A, B가 있을 때 A에 포함된 숫자를 섞어 새로운 수 C를 만들려고 함
- C는 A의 순열 중 하나일 것
- C는 0으로 시작 X
- 가능한 C중 B보다 작으면서 가장 큰 값 구하기
시간 제한
- 2초
입력
- A B
- 1≤A,B<10억
출력
- B보다 작은 C중 가장 큰 값
- 없다면 -1
접근법
- A는 최대 10자리 까지 가능
- A의 자릿수들을 배열에 담기
- 순열을 구해서 B와 비교할 것
- 10P10 ⇒ 2초 이내 가능
- 이때 배열 첫번째 원소 자리에는 0이 오는 경우는 제외할 것
코드
import java.io.*;
import java.util.ArrayList;
import java.util.StringTokenizer;
public class Main {
static int A, B;
static ArrayList<Integer> arr = new ArrayList<>();
static int size;
static boolean[] visited;
static int[] selected;
static int answer = -1;
static void recur(int cur) {
if (cur == size) {
if(arr.get(selected[0]) == 0) return;
int num = 0;
for (int i = size - 1, j = 1; i >= 0; i--) {
num += arr.get(selected[i]) * j;
j *= 10;
}
if(num > B) return;
answer = Math.max(answer, num);
return;
}
for (int i = 0; i < size; i++) {
if(visited[i]) continue;
visited[i] = true;
selected[cur] = i;
recur(cur + 1);
visited[i] = false;
}
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringTokenizer st;
st = new StringTokenizer(br.readLine());
A = Integer.parseInt(st.nextToken());
B = Integer.parseInt(st.nextToken());
int num = A;
while (num > 0) {
arr.add(num % 10);
num /= 10;
}
size = arr.size();
visited = new boolean[size];
selected = new int[size];
recur(0);
bw.write(String.valueOf(answer));
bw.flush();
bw.close();
br.close();
}
}
알고리즘 문제) BOJ 6603. 로또
문제 요약
- 1~49 중 수 6개를 고른다.
- 가장 유명한 전략은 49가지 수 중 k(>6)개의 수를 골라 집합 S를 만든 다음 그 수만 가지고 번호 선택
- 집합 S와 K개가 주어졌을 때 수를 고르는 모든 방법 구하기
시간 제한
- 1초
입력
- 테스트케이스 별로 한 줄에 k와 집합s(오름차순)가 주어짐
- 6<k<13
- 0이 입력되면 종료
출력
- 테스트 케이스 별로 수를 고르는 모든 방법 출력(사전 순)
- 테스트케이스 사이에는 빈 줄 출력
접근법
- 중복 없이 집합 S에서 6개 고르는 경우의 수 출력
코드
import java.io.*;
import java.util.StringTokenizer;
public class Main {
static int k;
static int[] arr;
static int[] selected = new int[6];
static StringBuilder sb = new StringBuilder();
static void recur(int cur, int start) {
if (cur == 6) {
for (int i = 0; i < 6; i++) {
sb.append(arr[selected[i]]+" ");
}
sb.append("\\n");
return;
}
for (int i = start; i < k; i++) {
selected[cur] = i;
recur(cur + 1, i + 1);
}
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringTokenizer st;
while (true) {
st = new StringTokenizer(br.readLine());
k = Integer.parseInt(st.nextToken());
if(k == 0) break;
arr = new int[k];
for (int i = 0; i < k; i++) {
arr[i] = Integer.parseInt(st.nextToken());
}
recur(0, 0);
sb.append("\\n");
}
bw.write(String.valueOf(sb));
bw.flush();
bw.close();
br.close();
}
}