📙[Algo] 24.02.25 알고리즘

알고리즘 문제) BOJ 28447. 마라탕 재료 고르기

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

문제 요약

• K개의 재료를 넣어서 마라맛을 최대로 하려고 한다.
  • Cij : 재료 i와 재료j를 같이 넣었을 때의 궁합
  • 마라맛 : 모든 재료 쌍의 궁합

시간 제한

• 1초

입력

• 재료의 수 N, 고른 재료의 수 K
  • 1≤N≤10
  • 1≤K≤N
• N개의 줄에 걸쳐 i+1번 줄에 i와 다른 재료들의 궁합을 나타내는 수열이 공백으로 구분되어 주어짐
  • Ci1, Ci2, …
    • -1000≤Cij≤1000
    • Cii = 0
    • Cij = Cji

출력

• K개의 재료만 사용한 마라탕의 맛의 최댓값?

접근법

1. 완전 탐색으로 생각하기
   • for문을 K개만큼 중첩한다. 만약 K가 3이라면
     • for i=1~i=N
       • for j= i+1~j=N
         • for k=j+1~k=N
           • arr[i][j] + arr[i][k] + arr[j][k] → 최대인 것 찾기
2. 백트랙킹즉 NCK를 찾는 문제!
   • 중첩 개수가 K에 따라 달라지므로 백트랙킹 사용!!

코드

import java.io.*;
import java.util.StringTokenizer;

public class Main {
    static int N, K; // N: 재료 수, K : 고를 재료 수
    static int[][] arr; // 재료 궁합 정보
    static int[] selected; // 선택된 재료
    static int answer = Integer.MIN_VALUE; // 마라탕 맛 -> 최댓값 갱신

    static void recur(int cur, int cnt) {

        // 개수 K개 초과해서 고른 것은 pass
        if(cnt > K) return;

        if (cur == N) {

            // 개수를 K개 미만으로 고른 경우
            if(cnt < K) return;

            // 선택된 재료 중 2개씩 쌍을 지어서 마라탕 맛 구하기
            int sum = 0;
            for (int i = 0; i < cnt - 1; i++) {
                for (int j = i + 1; j < cnt; j++) {
                    sum += arr[selected[i]][selected[j]];
                }
            }

            // 최댓값 갱신
            answer = Math.max(answer, sum);

            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());
        K = Integer.parseInt(st.nextToken());

        arr = new int[N][N];
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < N; j++) {
                arr[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        selected = new int[K + 1];
        recur(0, 0);

        bw.write(String.valueOf(answer));
        bw.flush();
        bw.close();
        br.close();
    }
}

 

알고리즘 문제) BOJ 24954. 물약 구매

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

문제 요약

• 1번~N번까지 번호가 매겨진 물약중 N종류의 물약을 모두 구매하려고 함
• 이때 특정 물약 구매시 다른 물약들을 할인
  • i번째 물약 구매시 pi종류의 다른 물약의 가격이 내려감(ci개)
  • 0이하로는 내려가지 않음(최소 동전 1개까지 내려감)
• 물약을 가장 싸게 샀을 때 비용 구하기
  • 순서가 중요

시간 제한

• 3초

입력

• 물약 종류 N
  • 2≤N≤10
• 물약의 가격 ci가 공백을 두고 주어짐(1≤i≤N)
  • 1≤ci≤1000
• 물약 할인 정보 N개가 주어짐
  • 즉 i번번째 물약구매시 할인정보가 다음과 같이 주어짐
    • pi가 주어짐 : 할인되는 물약 종류
      • 0≤pi<N-1
    • pi개 줄에 물약 번호 aj, 할인되는 가격 dj가 주어짐
      • i ≠ aj
      • 1≤dj≤1000
    ⇒ 즉, i번 물약을 구매하고 나면 aj가 동전 dj만큼 할인

출력

• 물약을 가장 싸게 샀을 때 동전이 몇 개 필요한지 출력

접근법

1. 완전 탐색으로 생각하기
   • 모든 종류를 사야하므로 → 순서를 적절히 조절해서 구매해야 함
   • 순열 구해서 매 케이스마다 필요한 동전 개수 최솟값으로 갱신

코드

import java.io.*;
import java.util.ArrayList;
import java.util.StringTokenizer;

public class Main {
    static int N; // 물약 개수
    static int[] prices; // 물약 구매시 필요한 동전 개수
    static int[] copiedPrices; // prices 배열 복사본
    static ArrayList<Discounts>[] dcInfo; // 할인 정보
    static int[] selected ; // 선택한 후보(순서)
    static boolean[] visited; // 방문 처리
    static int answer = Integer.MAX_VALUE; // 가장 싸게 구매 시 필요한 동전 개수

    static class Discounts {
        int p; // 할인되는 물약 번호
        int disc; // 할인되는 동전 개수

        Discounts(int p, int disc) {
            this.p = p;
            this.disc = disc;
        }
    }

    static void copyPrice() {
        for (int i = 0; i < N; i++) {
            copiedPrices[i] = prices[i];
        }
    }

    static void recur(int cur) {
        if (cur == N) {

            copyPrice();

            int coin = 0, sIdx;
            Discounts info;
            for (int i = 0; i < N; i++) {
                sIdx = selected[i];
                coin += copiedPrices[sIdx];
                for (int j = 0; j < dcInfo[sIdx].size(); j++) {
                    info = dcInfo[sIdx].get(j);
                    copiedPrices[info.p] -=  info.disc;
                    if(copiedPrices[info.p] < 1) copiedPrices[info.p] = 1;
                }
            }

            answer = Math.min(answer, coin);

            return;
        }

        for (int i = 0; i < N; 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;

        N = Integer.parseInt(br.readLine());

        prices = new int[N];
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            prices[i] = Integer.parseInt(st.nextToken());
        }

        dcInfo = new ArrayList[N];
        int pi, aj, dj;
        for (int i = 0; i < N; i++) {
            dcInfo[i] = new ArrayList<>();
            pi = Integer.parseInt(br.readLine());

            for (int j = 0; j < pi; j++) {
                st = new StringTokenizer(br.readLine());
                aj = Integer.parseInt(st.nextToken()) - 1;
                dj = Integer.parseInt(st.nextToken());
                dcInfo[i].add(new Discounts(aj, dj));
            }
        }

        selected = new int[N];
        visited = new boolean[N];
        copiedPrices = new int[N];
        recur(0);

        bw.write(String.valueOf(answer));
        bw.flush();
        bw.close();
        br.close();
    }
}