📙 Algorithm Solving/Java
📙[Algo] 24.02.23~24.02.24 알고리즘
혜덕hyeduck
2024. 2. 25. 14:52
알고리즘 문제) BOJ 19942. 다이어트
문제 요약
- 식재료 N개 중에서 단백질, 탄수화물, 지방, 비타민이 일정 이상 되도록 재료를 선할 때, 비용이 최소가 되는 경우 찾기
시간 제한
- 2초
입력
- 식재료 개수 N
- 3≤N≤15
- 단백질, 지방, 탄수화물, 비타민 최소 영양성분인 mp,mf,ms,mv가 주어짐
- 0≤mp,mf,ms,mv≤500
- mp+mf+ms+mv > 0
- 다음 N개의 줄에 i번째 식재료의 단백질, 지방, 탄수화물, 비타민과 가격이 주어짐 pi, fi, si, vi, ci
- 0≤pi,fi,si,vi,ci≤500
- 번호는 1번부터 시작
출력
- 최소비용 출력
- 최소 비용 식재료의 번호를 오름차순으로 출력
- 없다면 -1만 출력
접근법
- 1~N개를 골랐을 때 최소 기준을 충족하고, 그 중 최소 비용인 경우를 찾아야한다.
- N의 범위가 15까지 가능하므로 최대 32768가지 경우를 살핌…
코드
import java.io.*;
import java.util.ArrayList;
import java.util.Collections;
import java.util.StringTokenizer;
public class Main {
static int N;
static int[] standard;
static int[][] foods;
static int[] selected;
static ArrayList<String> ansFoods = new ArrayList<>();
static int answer = Integer.MAX_VALUE;
static void recur(int cur, int cnt) {
if (cur == N + 1) {
int p = 0, f = 0, s = 0, v = 0, c = 0;
for (int i = 0; i < cnt; i++) {
p += foods[selected[i]][0];
f += foods[selected[i]][1];
s += foods[selected[i]][2];
v += foods[selected[i]][3];
c += foods[selected[i]][4];
}
if (p < standard[0] || f < standard[1] || s < standard[2] || v < standard[3]) {
return;
}
if (answer >= c) {
if (answer > c) {
answer = c;
ansFoods.clear();
}
String str = "" ;
for (int i = 0; i < cnt; i++) {
str += selected[i] + " ";
}
ansFoods.add(str);
}
return;
}
selected[cnt] = cur;
recur(cur + 1, cnt + 1);
selected[cnt] = 0;
recur(cur + 1, cnt);
}
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());
standard = new int[4];
st = new StringTokenizer(br.readLine());
for (int i = 0; i < 4; i++) {
standard[i] = Integer.parseInt(st.nextToken());
}
foods = new int[N + 1][5];
for (int i = 1; i <= N; i++) {
st = new StringTokenizer(br.readLine());
for (int j = 0; j < 5; j++) {
foods[i][j] = Integer.parseInt(st.nextToken());
}
}
selected = new int[N];
recur(1, 0);
if (answer == Integer.MAX_VALUE) {
bw.write("-1");
} else {
bw.write(answer + "\\n");
Collections.sort(ansFoods);
bw.write(String.valueOf(ansFoods.get(0)));
}
bw.flush();
bw.close();
br.close();
}
}
알고리즘 문제) BOJ 1497. 기타콘서트
문제 요약
- 최대한 많은 곡을 제대로 연주하려고 할 때 필요한 기타의 최소 개수 구하기
- 만약 다 연주할 수 있다면 다 연주하는 쪽으로 필요한 기타 최소 개수 구하기
시간 제한
- 2초
입력
- 기타 개수 N 곡의 개수M
- 1≤N≤10
- 1≤M≤50
- N개의 줄에 기타 이름과 기타가 연주할 수 있는 곡의 정보가 주어짐
- Y : 연주 가능, N : 연주 불가능
- 기타 이름은 알파벳 대문자로 길이가 2이상 50 이하
- 기타 이름이 같은 경우는 X
출력
- 필요한 기타 개수 출력
- 만약 연주할 수 있는 곡이 없다면 -1 출력
접근법
- 기타를 선택하는 모든 경우의 수를 본다(N이 10이하므로 완탐 가능)
- 이때 연주할 수 있는 곡의 개수 최댓값을 갱신한다.
- 만약 같은 경우가 있다면 기타 개수가 최소인 쪽으로 기타 개수 갱신
코드
import java.io.*;
import java.util.Arrays;
import java.util.StringTokenizer;
public class Main {
static int N, M; // 기타 개수, 곡의 개수
static String[][] arr; // 기타 이름과 연주할 수 있는 곡 정보
static int[] selected; // 정답 후보를 담을 배열(후보의 인덱스를 원소로 갖는다)
static boolean[] visited; // 연주할 수 있는 곡의 개수 체크(이미 체크한 경우 중복 카운팅 방지)
static int answer = 1000000000; // 필요한 기타 개수(최솟값으로 갱신)
static int playSongs = 0; // 연주 간으한 곡 개수(최대값 갱신)
static void recur(int cur, int cnt) {
// cur : 현재 가리키고 있는 후보 인덱스
// cnt : 현재까지 정답 후보에 올려놓은 개수
// canPlay : 연주할 수 있는 곡의 개수
if (cur == N) {
// 후보군 끝까지 탐색했을 때
int canPlay = 0; // 연주할 수 있는 곡
for (int i = 0; i < cnt; i++) {
for (int j = 0; j < M; j++) {
if (arr[selected[i]][1].charAt(j) == 'Y') {
// 연주할 수 있다면
if (visited[j]) continue; // 이미 체크한 곡이라면 pass
visited[j] = true; // 아니라면 체크해주고
canPlay++; // 연주 가능한 곡 개수 +1
}
}
}
if (playSongs == canPlay) {
// 연주 가능한 곡이 현재까지 연주 가능 곡과 같다면
// 기타 개수 최솟값으로 갱신
answer = Math.min(answer, cnt);
} else if (playSongs < canPlay) {
// 연주 가능한 곡이 더 크다면 갱신해주고, 기타 개수도 현재 개수로 초기화
playSongs = canPlay;
answer = cnt;
}
// visited 배열 false로 초기화
Arrays.fill(visited, false);
return;
}
// 현재 가리키는 후보를 선택할 경우
selected[cnt] = cur;
recur(cur + 1, cnt + 1);
// 햔재 가리키는 후보를 패스할 경우
selected[cur] = -1;
recur(cur + 1, cnt);
}
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, M 입력 받기
st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
// 기타 이름과 연주곡 정보 입력 받기
arr = new String[N][2];
for (int i = 0; i < N; i++) {
st = new StringTokenizer(br.readLine());
arr[i][0] = st.nextToken();
arr[i][1] = st.nextToken();
}
selected = new int[N];
visited = new boolean[M];
recur(0, 0);
if (playSongs == 0) bw.write("-1");
else bw.write(String.valueOf(answer));
bw.flush();
bw.close();
br.close();
}
}
알고리즘 문제) BOJ 16457. 단풍잎 이야기
문제 요약
- m개의 퀘스트들이 주어지고 각각의 퀘스트는 k개의 스킬을 사용해야 함
- n개의 키에 어떤 스킬들을 배치할 때 가장 많은 양의 퀘스트를 깰 수 있는지 찾기
시간 제한
- 1초
입력
- 키의 개수 n, 퀘스트 개수 m, 퀘스트 당 사용해야하는 스킬 개수 k
- n은 10이하 양수
- k는 n이하 양수
- m은 100이하 양수
- m개의 줄에 각각 퀘스트들이 사용해야하는 스킬들이 주어짐
- 스킬이름은 1~2n의 정수
출력
- 가장 최적의 키배치를 했을 때 최대로 깰 수 있는 퀘스트 개수?
접근법
키에는 1부터 2n의 키를 배치할 수 있다.
즉, 1~2n의 키중 n개를 배치하는 경우를 찾고, 이때 꺨수 있는 퀘스트 수를 카운팅하고 최댓값으로 갱신한다.
백트랙킹 가지치기로 cnt > n인 경우 return 하기
코드
import java.io.*;
import java.util.StringTokenizer;
public class Main {
static int N, M, K; // 키 개수, 퀘스트 개수, 스킬 수
static int[][] quests; // 퀘스트 스킬 정보
static int[] selected; // 배치한 스킬 이름(번호)
static int answer = 0; // 최대로 깰 수 있는 스킬 개수
static void recur(int cur, int cnt) {
// 키 배치를 N개 초과할 때 return -> N개만 배치 가능하므로
if (cnt > N) return;
if (cur == 2 * N + 1) {
// 키가 2*N까지 배치될 수 있기때문에 다 배치하고나서 2*N + 1일 때 체크
// 깰 수 있는 퀘스트 수 카운팅
int check, clear = 0;
for (int i = 0; i < M; i++) {
// 퀘스트 별로 돌면서
check = 0; // 깰 수 있는 스킬 수를 체크
for (int j = 0; j < cnt; j++) {
for (int l = 0; l < K; l++) {
if (quests[i][l] == selected[j]) check++;
}
}
// check가 K와 같다면 클리한 것이므로 클리어 수 증가
if (check >= K) clear++;
}
answer = Math.max(answer, clear);
return;
}
selected[cnt] = cur;
recur(cur + 1, cnt + 1);
recur(cur + 1, cnt);
}
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());
K = Integer.parseInt(st.nextToken());
// 퀘스트 스킬 정보 입력
quests = new int[M][K];
for (int i = 0; i < M; i++) {
st = new StringTokenizer(br.readLine());
for (int j = 0; j < K; j++) {
quests[i][j] = Integer.parseInt(st.nextToken());
}
}
selected = new int[2 * N];
recur(1, 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개를 섞었을 때의 경우들을 살펴본다
- 그때 곰두리 색의 차이가 가장 적은 경우로 차이값을 갱신한다.
코드
import java.io.*;
import java.util.StringTokenizer;
public class Main {
static int N; // 물감 개수
static int[][] colors; // 물감들의 RGB 정보
static int[] gomduri; // 곰두리 색의 RGB 정보
static int answer = Integer.MAX_VALUE; // 차이값
static void recur(int cur, int cnt, int r, int g, int b) {
if (cnt > 7) return; // 개수가 7개를 넘어가는 순간 pass
if (cur == N) {
// 선택한 개수가 1개 이하 또는 8개 이상일 경우 pass
if (cnt < 2) {
return;
}
// 곰두리색과의 차이값 갱신
answer = Math.min(answer
, Math.abs(gomduri[0] - r / cnt) + Math.abs(gomduri[1] - g / cnt) + Math.abs(gomduri[2] - b / cnt));
return;
}
// 색상을 선택한 경우
recur(cur + 1, cnt + 1
, r + colors[cur][0], g + colors[cur][1], b + colors[cur][2]);
// 색상을 선택하지 않은 경우
recur(cur + 1, cnt, r, g, b);
}
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()); // 물감 개수 입력 받기
// 물감 RGB 정보 입력 받기
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());
}
// 곰두리 색 RGB 정보 입력 받기
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());
recur(0, 0, 0, 0, 0);
bw.write(String.valueOf(answer));
bw.flush();
bw.close();
br.close();
}
}
알고리즘 문제) BOJ 19949. 영재의 시험
문제 요약
- 5지선다 객관식 10문제의 시험에서
- 3개의 연속된 문제는 같지 않게 답한다는 규칙을 이용해서 찍었을 때 점수가 5점 이상일 경우의 수 구하기
시간 제한
- 1초
입력
- 시험의 정답이 첫 줄에 주어짐
출력
- 점수가 5점 이상일 경우의 수 출력
접근법
- 완전 탐색으로 생각하기
- 10중 for문 사용해서 정답이 5점이 이상 일 경우 카운트
코드
import java.io.*;
import java.util.StringTokenizer;
public class Main {
static int[] arr; // 문제의 정답
static int[] selected; // 선택한 정답
static int answer; // 정답 개수
static void recur(int cur, int correct) {
// cur : 지금까지 선택한 위치
// correct : 맞은 개수
if (cur == 10) {
// 맞은 개수가 5개 미만이면 pass
if(correct < 5) return;
// 3개 연속인 답이 있는지 체크
boolean check = true;
for (int i = 0; i <= 7; i++) {
if (selected[i] == selected[i + 1] && selected[i] == selected[i + 2]) {
check = false;
break;
}
}
// 조건 충족시 카운팅
if(check) answer++;
return;
}
for (int i = 1; i <= 5; i++) {
selected[cur] = i;
if (arr[cur] == i) {
// 정답이 갖다면 correct + 1
recur(cur + 1, correct + 1);
} else {
// 갖지 않다면 correct
recur(cur + 1, correct);
}
}
}
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 = new StringTokenizer(br.readLine());
arr = new int[10];
for (int i = 0; i < 10; i++) {
arr[i] = Integer.parseInt(st.nextToken());
}
selected = new int[10];
recur(0,0);
bw.write(String.valueOf(answer));
bw.flush();
bw.close();
br.close();
}
}
알고리즘 문제) BOJ 14501. 퇴사
문제 요약
- N+1일째 되는 날 퇴사를 하기 위해서, 남은 N일 동안 최대한 많은 상담
- 하루에 하나씩 서로 다른 사람의 상담
- 담을 완료하는데 걸리는 기간 Ti와 상담을 했을 때 받을 수 있는 금액 Pi
시간 제한
- 2초
입력
- N (1 ≤ N ≤ 15)
- N개의 줄에 Ti와 Pi
- 1 ≤ Ti ≤ 5, 1 ≤ Pi ≤ 1,000
출력
- 백준이가 얻을 수 있는 최대 이익
코드
import java.io.*;
import java.util.StringTokenizer;
public class Main {
static int N; // 상담 개수
static int[][] schedules; // 상담 리스트
static int[] selected; // 선택된 스케쥴
static int answer = 0; // 최대 이익
static void recur(int cur, int cnt) {
if (cur == N + 1) {
int nextDay = 0;
int profit = 0;
boolean check = true;
for (int i = 0; i < cnt; i++) {
if (selected[i] < nextDay){
check = false;
break;
}
nextDay = selected[i] + schedules[selected[i]][0];
if (nextDay - 1 > N){
check = false;
break;
}
profit += schedules[selected[i]][1];
}
if(!check) return;
answer = Math.max(answer, profit);
return;
}
// 스케쥴 선택
selected[cnt] = cur;
recur(cur + 1, cnt + 1);
recur(cur + 1, cnt);
}
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());
// 상담 리스트 입력 받기
schedules = new int[N + 1][2];
for (int i = 1; i <= N; i++) {
st = new StringTokenizer(br.readLine());
schedules[i][0] = Integer.parseInt(st.nextToken());
schedules[i][1] = Integer.parseInt(st.nextToken());
}
selected = new int[N];
recur(1, 0);
bw.write(String.valueOf(answer));
bw.flush();
bw.close();
br.close();
}
}