📙[Algo] 24.02.23~24.02.24 알고리즘

알고리즘 문제) BOJ 19942. 다이어트

• 링크 : https://www.acmicpc.net/problem/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. 기타콘서트

• 링크 : https://www.acmicpc.net/problem/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. 단풍잎 이야기

• 링크 : https://www.acmicpc.net/problem/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. 미술가 미미

• 링크 : https://www.acmicpc.net/problem/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. 영재의 시험

• 링크 : https://www.acmicpc.net/problem/19949

문제 요약

• 5지선다 객관식 10문제의 시험에서
• 3개의 연속된 문제는 같지 않게 답한다는 규칙을 이용해서 찍었을 때 점수가 5점 이상일 경우의 수 구하기

시간 제한

• 1초

입력

• 시험의 정답이 첫 줄에 주어짐

출력

• 점수가 5점 이상일 경우의 수 출력

접근법

1. 완전 탐색으로 생각하기
   • 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. 퇴사

• 링크 : https://www.acmicpc.net/problem/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();
    }
}