더 이상 물러설 곳이 없다

www.acmicpc.net/problem/2493

문제

KOI 통신연구소는 레이저를 이용한 새로운 비밀 통신 시스템 개발을 위한 실험을 하고 있다. 실험을 위하여 일직선 위에 N개의 높이가 서로 다른 탑을 수평 직선의 왼쪽부터 오른쪽 방향으로 차례로 세우고, 각 탑의 꼭대기에 레이저 송신기를 설치하였다. 모든 탑의 레이저 송신기는 레이저 신호를 지표면과 평행하게 수평 직선의 왼쪽 방향으로 발사하고, 탑의 기둥 모두에는 레이저 신호를 수신하는 장치가 설치되어 있다. 하나의 탑에서 발사된 레이저 신호는 가장 먼저 만나는 단 하나의 탑에서만 수신이 가능하다. 

예를 들어 높이가 6, 9, 5, 7, 4인 다섯 개의 탑이 수평 직선에 일렬로 서 있고, 모든 탑에서는 주어진 탑 순서의 반대 방향(왼쪽 방향)으로 동시에 레이저 신호를 발사한다고 하자. 그러면, 높이가 4인 다섯 번째 탑에서 발사한 레이저 신호는 높이가 7인 네 번째 탑이 수신을 하고, 높이가 7인 네 번째 탑의 신호는 높이가 9인 두 번째 탑이, 높이가 5인 세 번째 탑의 신호도 높이가 9인 두 번째 탑이 수신을 한다. 높이가 9인 두 번째 탑과 높이가 6인 첫 번째 탑이 보낸 레이저 신호는 어떤 탑에서도 수신을 하지 못한다.

탑들의 개수 N과 탑들의 높이가 주어질 때, 각각의 탑에서 발사한 레이저 신호를 어느 탑에서 수신하는지를 알아내는 프로그램을 작성하라.

입력

첫째 줄에 탑의 수를 나타내는 정수 N이 주어진다. N은 1 이상 500,000 이하이다. 둘째 줄에는 N개의 탑들의 높이가 직선상에 놓인 순서대로 하나의 빈칸을 사이에 두고 주어진다. 탑들의 높이는 1 이상 100,000,000 이하의 정수이다.

출력

첫째 줄에 주어진 탑들의 순서대로 각각의 탑들에서 발사한 레이저 신호를 수신한 탑들의 번호를 하나의 빈칸을 사이에 두고 출력한다. 만약 레이저 신호를 수신하는 탑이 존재하지 않으면 0을 출력한다.

예제 입력 1

5 6 9 5 7 4

예제 출력 1

0 0 2 2 4

풀이 .

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Stack;
import java.util.StringTokenizer;

class Pair {
    int num, height;
    Pair(int num, int height) {
        this.num = num;
        this.height = height;
    }
}

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        StringBuilder sb = new StringBuilder();
        Stack<Pair> stk = new Stack<>();

        int n = Integer.parseInt(st.nextToken());
        st = new StringTokenizer(br.readLine());
        for(int i = 1; i <= n; i++) {
            int height = Integer.parseInt(st.nextToken());

            while(!stk.isEmpty()) {
                if(stk.peek().height > height) {
                    sb.append(stk.peek().num + " ");
                    break;
                }
                stk.pop();
            }
            if(stk.isEmpty()) {
                sb.append("0 ");
            }
            stk.push(new Pair(i, height));

        }
        System.out.println(sb.toString());
    }
}

어떤 탑의 왼쪽에 있는 탑들은 해당 탑보다 높이가 낮다면 전부 버려도 무방하다.

(어차피 레이저는 오른쪽에서 오고 해당 탑에서 막히거나 쭉 지나가거나 둘 중 하나일 테니까)

즉, 새로운 탑을 입력 받을 때마다 기존에 존재하는 탑들의 삭제 여부를 정할 수 있다.

www.acmicpc.net/problem/2800

문제

어떤 수식이 주어졌을 때, 괄호를 제거해서 나올 수 있는 서로 다른 식의 개수를 계산하는 프로그램을 작성하시오.

이 수식은 괄호가 올바르게 쳐져 있다. 예를 들면, 1+2, (3+4), (3+4*(5+6))와 같은 식은 괄호가 서로 쌍이 맞으므로 올바른 식이다.

하지만, 1+(2*3, ((2+3)*4 와 같은 식은 쌍이 맞지 않는 괄호가 있으므로 올바른 식이 아니다.

괄호를 제거할 때는, 항상 쌍이 되는 괄호끼리 제거해야 한다.

예를들어 (2+(2*2)+2)에서 괄호를 제거하면, (2+2*2+2), 2+(2*2)+2, 2+2*2+2를 만들 수 있다. 하지만, (2+2*2)+2와 2+(2*2+2)는 만들 수 없다. 그 이유는 쌍이 되지 않는 괄호를 제거했기 때문이다.

어떤 식을 여러 쌍의 괄호가 감쌀 수 있다.

입력

첫째 줄에 음이 아닌 정수로 이루어진 수식이 주어진다. 이 수식은 괄호가 올바르게 쳐져있다. 숫자, '+', '*', '-', '/', '(', ')'로만 이루어져 있다. 수식의 길이는 최대 200이고, 괄호 쌍은 적어도 1개, 많아야 10개이다. 

출력

올바른 괄호 쌍을 제거해서 나올 수 있는 서로 다른 식을 사전 순으로 출력한다.

예제 입력 1

(0/(0))

예제 출력 1

(0/0)

0/(0)

0/0

풀이 .

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    static BufferedReader br = null;
    static StringBuilder sb = null;
    static Stack<Integer> stk = null;
    static Set<String> set = null;

    static String str = null;
    static int[] pair = null;  // 괄호 쌍 서로의 인덱스 저장하는 배열
    static boolean[] check = null;  // 나와 쌍을 맺는 괄호 지울 것인지

    public static void dfs(int deptNow, int dept) {
        if(deptNow == dept) {
            set.add(sb.toString());
            return;
        }

        char ch = str.charAt(deptNow);
        if(ch == '(') {
            check[deptNow] = true;
            dfs(deptNow+1, dept);  // 해당 쌍의 괄호를 지우는 경우
            check[deptNow] = false;
        }

        if(ch == ')' && check[pair[deptNow]]) {  // 나와 쌍인 '('가 지워져있는지 체크
            check[deptNow] = true;  // 사실 이어져있는 괄호 쌍은 하나뿐이라 여기서 굳이 check 건드릴 필요는 없긴 함
            dfs(deptNow+1, dept);
            check[deptNow] = false;
        }else {  // 괄호 안 지우는 경우 or 숫자일 경우
            sb.append(ch);
            dfs(deptNow+1, dept);
            sb.deleteCharAt(sb.length() - 1);
        }
    }

    public static void main(String[] args) throws IOException {
        br = new BufferedReader(new InputStreamReader(System.in));
        sb = new StringBuilder();
        stk = new Stack<>();
        set = new HashSet<>();

        str = br.readLine();
        pair = new int[str.length()];
        check = new boolean[str.length()];

        int len = str.length();
        for(int i = 0; i < len; i++) {  // 자신과 쌍을 이루는 괄호의 인덱스를 갖도록 함
            char ch = str.charAt(i);
            if(ch == '(') {
                stk.push(i);
            }else if(ch == ')') {
                pair[i] = stk.peek();  // 1, 3 인덱스에 '(', ')' 쌍이 위치할 경우
                pair[stk.peek()] = i;  // pair[1] = 3, pair[3] = 1 이렇게
                stk.pop();
            }
        }

        dfs(0, str.length());
        set.remove(str);  // 괄호를 하나도 삭제하지 않은 경우는 제외
        ArrayList<String> list = new ArrayList<>(set);
        Collections.sort(list);
        for (String s : list) {
            sb.append(s).append("\n");
        }
        System.out.println(sb.toString());
    }
}

아직 스택 사용이 익숙하지 않은 듯 하다.

구현에서 애를 많이 먹었다.

1. int[] pair을 사용해서 괄호들에 대하여 자신과 쌍을 이루는 괄호의 인덱스를 기억하도록 한다.

2. 백트래킹을 통해 괄호쌍을 지우는 경우와 지우지 않는 경우 모두를 수행한다.

사전순 출력 조건을 위해 정렬을 하려고 ArrayList를 사용했는데 이것 때문에 22%에서 틀렸습니다가 떴다.

반례를 찾아서 넣어보니 똑같은 정답이 중복 출력되는 문제가 있었다.

괄호가 여럿이 겹쳐있는 경우에는 다른 괄호쌍을 지우더라도 결과가 같아질 수 있기 때문에 중복 정답이 담기게 된다.

(ex : (((3)))의 경우에서 첫번째, 두번째, 세번째 괄호쌍을 지운 각각의 경우는 모두 ((3))으로 같다)

정답 케이스를 Set에 담고 그 Set으로 ArrayList를 만들어서 정렬하는 방식으로 문제를 해결했다.

www.acmicpc.net/problem/2504

문제

4개의 기호 ‘(’, ‘)’, ‘[’, ‘]’를 이용해서 만들어지는 괄호열 중에서 올바른 괄호열이란 다음과 같이 정의된다.

1. 한 쌍의 괄호로만 이루어진 ‘()’와 ‘[]’는 올바른 괄호열이다. 
2. 만일 X가 올바른 괄호열이면 ‘(X)’이나 ‘[X]’도 모두 올바른 괄호열이 된다. 
3. X와 Y 모두 올바른 괄호열이라면 이들을 결합한 XY도 올바른 괄호열이 된다.

예를 들어 ‘(()[[]])’나 ‘(())[][]’ 는 올바른 괄호열이지만 ‘([)]’ 나 ‘(()()[]’ 은 모두 올바른 괄호열이 아니다. 우리는 어떤 올바른 괄호열 X에 대하여 그 괄호열의 값(괄호값)을 아래와 같이 정의하고 값(X)로 표시한다. 

1. ‘()’ 인 괄호열의 값은 2이다.
2. ‘[]’ 인 괄호열의 값은 3이다.
3. ‘(X)’ 의 괄호값은 2×값(X) 으로 계산된다.
4. ‘[X]’ 의 괄호값은 3×값(X) 으로 계산된다.
5. 올바른 괄호열 X와 Y가 결합된 XY의 괄호값은 값(XY)= 값(X)+값(Y) 로 계산된다.

예를 들어 ‘(()[[]])([])’ 의 괄호값을 구해보자.  ‘()[[]]’ 의 괄호값이 2 + 3×3=11 이므로  ‘(()[[ ]])’의 괄호값은 2×11=22 이다. 그리고  ‘([])’의 값은 2×3=6 이므로 전체 괄호열의 값은 22 + 6 = 28 이다.

여러분이 풀어야 할 문제는 주어진 괄호열을 읽고 그 괄호값을 앞에서 정의한대로 계산하여 출력하는 것이다.

입력

첫째 줄에 괄호열을 나타내는 문자열(스트링)이 주어진다. 단 그 길이는 1 이상, 30 이하이다.

출력

첫째 줄에 그 괄호열의 값을 나타내는 정수를 출력한다. 만일 입력이 올바르지 못한 괄호열이면 반드시 0을 출력해야 한다. 

예제 입력 1

(()[[]])([])

예제 출력 1

28

풀이 .

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Stack;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] arr = br.readLine().split("");

        int len = arr.length;
        int SL = 0, LL  = 0;  // small left, large left

        Stack<String> stk = new Stack<>();
        for(int i = 0; i < len; i++) {  // () []를 숫자로 먼저 치환
            String str = arr[i];

            if(str.equals("(")) {
                SL += 1;
                stk.push(str);
            }else if(str.equals("[")) {
                LL += 1;
                stk.push(str);
            }else if(str.equals(")")) {
                if(SL == 0 || stk.peek().equals("[")) {
                    System.out.println(0);
                    return;
                }

                if(stk.peek().equals("(")) {
                    SL -= 1;
                    stk.pop();
                    stk.push("2");
                }else {
                    SL -= 1;
                    stk.push(str);
                }
            }else if(str.equals("]")) {
                if(LL == 0 || stk.peek().equals("(")) {
                    System.out.println(0);
                    return;
                }

                if(stk.peek().equals("[")) {
                    LL -= 1;
                    stk.pop();
                    stk.push("3");
                }else {
                    LL -= 1;
                    stk.push(str);
                }
            }
        }

        if(SL != 0 || LL != 0) {
            System.out.println(0);
            return;
        }

        Stack<String> temp = new Stack<>();
        while(!stk.isEmpty()) {  // 맨 밑부터 순서대로 보기 위해 잠시 다른 스택으로 옮김
            temp.push(stk.pop());
        }

        while(!temp.isEmpty()) {  // 올바르지 않은 괄호에 대해서는 이미 모두 처리했으므로 더 이상 볼 필요 없음
            String str = temp.pop();

            if(str.equals("(")) {
                stk.push(str);
            }else if(str.equals("[")) {
                stk.push(str);
            }else if(str.equals(")")) {
                int sum = 0;
                while(!stk.peek().equals("(")) {
                    int num = Integer.parseInt(stk.pop());
                    sum += num;
                }
                stk.pop();  // "(" 제거
                stk.push(String.valueOf(sum * 2));
            }else if(str.equals("]")) {
                int sum = 0;
                while(!stk.peek().equals("[")) {
                    int num = Integer.parseInt(stk.pop());
                    sum += num;
                }
                stk.pop();  // "[" 제거
                stk.push(String.valueOf(sum * 3));
            }else {  // 숫자는 그냥 넣는다
                stk.push(str);
            }
        }

        int ans = 0;
        while(!stk.isEmpty()) {  // 모든 괄호 처리 후 남은 숫자들 더함
            ans += Integer.parseInt(stk.pop());
        }
        System.out.println(ans);
    }
}

스택을 이용한 구현 문제.

방법 자체는 어렵지 않지만 구현 멍청이인 나에게는 힘겨웠던 문제.

내 승모근을 잔뜩 경직시키고 뒤통수를 예열시킨 문제.

www.acmicpc.net/problem/1935

문제

후위 표기식과 각 피연산자에 대응하는 값들이 주어져 있을 때, 그 식을 계산하는 프로그램을 작성하시오.

입력

첫째 줄에 피연산자의 개수(1 ≤ N ≤ 26) 가 주어진다. 그리고 둘째 줄에는 후위 표기식이 주어진다. (여기서 피연산자는 A~Z의 영대문자이며, A부터 순서대로 N개의 영대문자만이 사용되며, 길이는 100을 넘지 않는다) 그리고 셋째 줄부터 N+2번째 줄까지는 각 피연산자에 대응하는 값이 주어진다. (3번째 줄에는 A에 해당하는 값, 4번째 줄에는 B에 해당하는값 , 5번째 줄에는 C ...이 주어진다, 그리고 피연산자에 대응 하는 값은 정수이다)

출력

계산 결과를 소숫점 둘째 자리까지 출력한다.

예제 입력 1

5

ABC*+DE/-

1 2 3 4 5

예제 출력 1

6.20

예제 입력 2

1

AA+A+

1

예제 출력 2

3.00

풀이 .

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Stack;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        String prefix = br.readLine();

        int[] arr = new int[n];
        for(int i = 0; i < n; i++) {
            arr[i] = Integer.parseInt(br.readLine());
        }

        Stack<Double> operand = new Stack<>();
        int len = prefix.length();
        for(int i = 0; i < len; i++) {
            char ch = prefix.charAt(i);
            if('A' <= ch && ch <= 'Z') {  // operand
                double d = arr[ch - 'A'];
                operand.push(d);
            }else {  // operator
                double d1 = operand.pop();
                double d2 = operand.pop();
                double d3 = 0.0;
                switch(ch) {
                    case '+' :
                        d3 = d2 + d1;
                        break;
                    case '-' :
                        d3 = d2 - d1;
                        break;
                    case '*' :
                        d3 = d2 * d1;
                        break;
                    case '/' :
                        d3 = d2 / d1;
                        break;
                }
                operand.push(d3);
            }
        }
        System.out.printf("%.2f", operand.pop());
    }
}

피연산자의 값을 따로 저장하는 배열을 둔다.

명령어를 순회하면서 피연산자는 넣고 연산자 나오면 꺼내고 연산하여 다시 넣는다.

www.acmicpc.net/problem/1920

문제

N개의 정수 A[1], A[2], …, A[N]이 주어져 있을 때, 이 안에 X라는 정수가 존재하는지 알아내는 프로그램을 작성하시오.

입력

첫째 줄에 자연수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들이 A안에 존재하는지 알아내면 된다. 모든 정수의 범위는 -231 보다 크거나 같고 231보다 작다.

출력

M개의 줄에 답을 출력한다. 존재하면 1을, 존재하지 않으면 0을 출력한다.

예제 입력 1

5

4 1 5 2 3

5

1 3 7 9 5

예제 출력 1

1

1

0

0

1

풀이 .

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
    public static boolean bSearch(int[] arr, int target) {
        int min = 0;
        int max = arr.length - 1;

        while(min <= max) {
            int mid = (min + max) / 2;

            if(arr[mid] == target) {
                return true;
            }else if(arr[mid] > target) {
                max = mid - 1;
            }else if(arr[mid] < target) {
                min = mid + 1;
            }
        }
        return false;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        StringBuilder sb = new StringBuilder();

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

        int m = Integer.parseInt(br.readLine());
        st = new StringTokenizer(br.readLine());
        for(int i = 0; i < m; i++) {
            int target = Integer.parseInt(st.nextToken());
            if(bSearch(arr, target)) {
                sb.append("1\n");
            }else {
                sb.append("0\n");
            }
        }
        System.out.println(sb.toString());
    }
}

이분탐색 문제.

www.acmicpc.net/problem/1874

문제

스택 (stack)은 기본적인 자료구조 중 하나로, 컴퓨터 프로그램을 작성할 때 자주 이용되는 개념이다. 스택은 자료를 넣는 (push) 입구와 자료를 뽑는 (pop) 입구가 같아 제일 나중에 들어간 자료가 제일 먼저 나오는 (LIFO, Last in First out) 특성을 가지고 있다.

1부터 n까지의 수를 스택에 넣었다가 뽑아 늘어놓음으로써, 하나의 수열을 만들 수 있다. 이때, 스택에 push하는 순서는 반드시 오름차순을 지키도록 한다고 하자. 임의의 수열이 주어졌을 때 스택을 이용해 그 수열을 만들 수 있는지 없는지, 있다면 어떤 순서로 push와 pop 연산을 수행해야 하는지를 알아낼 수 있다. 이를 계산하는 프로그램을 작성하라.

입력

첫 줄에 n (1 ≤ n ≤ 100,000)이 주어진다. 둘째 줄부터 n개의 줄에는 수열을 이루는 1이상 n이하의 정수가 하나씩 순서대로 주어진다. 물론 같은 정수가 두 번 나오는 일은 없다.

출력

입력된 수열을 만들기 위해 필요한 연산을 한 줄에 한 개씩 출력한다. push연산은 +로, pop 연산은 -로 표현하도록 한다. 불가능한 경우 NO를 출력한다.

예제 입력 1

8 4 3 6 8 7 5 2 1

예제 출력 1

+ + + + - - + + - + + - - - - -

예제 입력 2

5 1 2 5 3 4

예제 출력 2

NO

풀이 .

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Stack;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        Stack<Integer> stk = new Stack<>();
        int n = Integer.parseInt(br.readLine());

        int lastPush = 0;
        while(n-- > 0) {
            int target = Integer.parseInt(br.readLine());

            if(stk.isEmpty()) {
                int len = target - lastPush;
                for(int i = 0; i < len; i++) {
                    stk.push(++lastPush);
                    sb.append("+").append("\n");
                }
                stk.pop();
                sb.append("-").append("\n");
            }else {
                if(stk.peek() == target) {
                    stk.pop();
                    sb.append("-").append("\n");
                }else if(stk.peek() > target) {
                    System.out.println("NO");
                    return;
                }else if(stk.peek() < target) {
                    int len = target - lastPush;
                    for(int i = 0; i < len; i++) {
                        stk.push(++lastPush);
                        sb.append("+").append("\n");
                    }
                    stk.pop();
                    sb.append("-").append("\n");
                }
            }
        }
        System.out.println(sb.toString());
    }
}

무식하게 구현했다.

더 똑똑한 방법이 있을 거 같긴 하다.

www.acmicpc.net/problem/1943

문제

윤화와 준희는 솔선수범하여 쓰레기를 줍는 착한 일을 하였다. 원장선생님께서는 윤화와 준희를 칭찬하시고 과자나 사 먹으라고 하시며 동전 몇 개를 윤화와 준희에게 건네 주었다.

그런데 돈을 받은 윤화와 준희는 좋아하기보다 고민에 빠지고 말았다. 원장선생님께 받은 이 돈을 어떻게 나누어 할지 고민에 빠진 것이다. 두 사람 모두 상대방이 자기보다 1원이라도 더 받는 것은 도저히 인정할 수 없어 한다. 따라서 돈을 똑같이 둘로 나누어 가져야 두 사람이 모두 만족할 수 있게 된다.

하지만 두 사람에게 돈을 똑같이 나누는 것이 불가능한 경우도 있다. 예를 들어 500원짜리 1개와 50원짜리 1개를 받았다면, 이 돈을 두 사람이 똑같이 나누어 가질 수는 없다. 물론 동전을 반으로 잘라서 나누어 가질 수도 있겠지만 그러면 돈으로서의 가치를 잃기 때문에 그렇게 할 수는 없다.

이제 우리가 할 일은 다음과 같다. 원장 선생님께서 N가지 종류의 동전을 각각 몇 개씩 주셨을 때, 그 돈을 반으로 나눌 수 있는지 없는지 판단하는 것이다.

입력

세 개의 입력이 주어진다. 각 입력의 첫째 줄에 동전의 종류 N(1≤N≤100)이 주어진다. 각 입력의 둘째 줄부터 N+1째 줄까지 각각의 동전의 금액과 개수가 빈 칸을 사이에 두고 주어진다. 단, 원장선생님께서 주신 금액의 총 합은 100,000원을 넘지 않는다.

출력

첫째 줄부터 세 줄에 걸쳐, 각 입력에 대하여 반으로 나누는 것이 가능하면 1, 불가능하면 0을 출력한다.

예제 입력 1

2

500 1

50 1

3

100 2

50 1

10 5

3

1 1

2 1

3 1

예제 출력 1

0

1

1

풀이 .

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

class Coin {
    int value, quantity;
    Coin(int value, int quantity) {
        this.value = value;
        this.quantity = quantity;
    }
}

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = null;

        int T = 3;
        while(T-- > 0) {
            int n = Integer.parseInt(br.readLine());
            Coin[] coins = new Coin[n+1];  // 원장님이 주는 금액의 최대는 10만원
            boolean[] dp = new boolean[100001];  // i원 만들기 가능?

            int total = 0;
            for(int i = 1; i <= n; i++) {
                st = new StringTokenizer(br.readLine());
                int value = Integer.parseInt(st.nextToken());
                int quantity = Integer.parseInt(st.nextToken());
                coins[i] = new Coin(value, quantity);
                total += value * quantity;  // 받은 총 금액 구함
                for(int j = 1; j <= quantity; j++) {
                    dp[value * j] = true;  // 각 종류의 동전으로 만들 수 있는 액수 먼저 체크
                }
            }

            // 굳이 dp[] 다 안 채워도 되는 경우
            if(total % 2 == 1) {
                System.out.println(0);
                continue;
            }else if(dp[total / 2]) {
                System.out.println(1);
                continue;
            }

            // 주어진 동전으로 (total / 2)원을 만들 수 있는지 확인하면 될 듯?
            dp[0] = true;
            for(int i = 1; i <= n; i++) {
                int v = coins[i].value;
                int q = coins[i].quantity;

                for(int j = total/2; j >= v; j--) {
                    if(dp[j - v]) {  // dp[j-v]가 가능해야 거기에 동전 하나씩 더해서 다음 액수를 가능하게 만들지

                        // (j-v)원부터 동전 v를 하나씩 사용하는 것
                        for(int k = 1; k <= q; k++) {
                            if(j - v + v * k > total/2) break;  // dp[total/2] 이상으로는 어차피 채울 필요 없음
                            dp[j - v + v * k] = true;
                        }
//                        // 이게 이말임
//                        for(int k = 0; k < quantity; k++) {
//                            dp[j + value * k] = true;
//                        }
                    }
                }
            }
            System.out.println(dp[total / 2] ? 1 : 0);
        }
    }
}

DP로 푸는 냅색 문제.

동전을 하나씩 사용하여 total/2 ~ v에 대한 검사를 한다.

1. 0원까지 안 하고 v까지만 검사하는 이유? 

해당 동전을 1개만 사용해도 v-1원보다는 크니까

2. v~total/2가 아니라 total/2~v로 내려오면서 검사하는 이유?

냅색 문제에서 흔히 발생하는 오류를 피하기 위함.

오름차순으로 검사를 하면 이전에 이미 사용한 동전에 의해 true가 된 것을 가지고 동전을 또 사용해서 다음값을 true로 만든다.

결국 1원짜리 하나만 있어도 모든 dp[]가 true가 되어버린다.

이것을 막기 위해 큰 금액부터 검사.

3. if(dp[j - v]) 하는 이유?

v의 값을 가지는 동전 q개를 사용하려는 상황.

dp[j-v] 까지는 완성이 되어있어야 동전 1~q개를 사용하면서 dp[j], dp[j+v], ... , dp[j + (q-1)v]을 만들 수 있다.

dp 테이블에 대한 정의도 어려웠고 채우는 것도 어려웠다.

그냥 다 어려웠다..

www.acmicpc.net/problem/12865

문제

이 문제는 아주 평범한 배낭에 관한 문제이다.

한 달 후면 국가의 부름을 받게 되는 준서는 여행을 가려고 한다. 세상과의 단절을 슬퍼하며 최대한 즐기기 위한 여행이기 때문에, 가지고 다닐 배낭 또한 최대한 가치 있게 싸려고 한다.

준서가 여행에 필요하다고 생각하는 N개의 물건이 있다. 각 물건은 무게 W와 가치 V를 가지는데, 해당 물건을 배낭에 넣어서 가면 준서가 V만큼 즐길 수 있다. 아직 행군을 해본 적이 없는 준서는 최대 K만큼의 무게만을 넣을 수 있는 배낭만 들고 다닐 수 있다. 준서가 최대한 즐거운 여행을 하기 위해 배낭에 넣을 수 있는 물건들의 가치의 최댓값을 알려주자.

입력

첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000)가 주어진다.

입력으로 주어지는 모든 수는 정수이다.

출력

한 줄에 배낭에 넣을 수 있는 물건들의 가치합의 최댓값을 출력한다.

예제 입력 1

4 7

6 13

4 8

3 6

5 12

예제 출력 1

14

풀이 .

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int k = Integer.parseInt(st.nextToken());

        int[] W = new int[n+1];
        int[] V = new int[n+1];
        int[][] dp = new int[n+1][k+1];  // dp[n][k] = 1~N개의 물건으로 무게제한 K 범위에서 가능한 최대 V
        for(int i = 1; i <= n; i++) {
            st = new StringTokenizer(br.readLine());
            int w = Integer.parseInt(st.nextToken());
            int v = Integer.parseInt(st.nextToken());
            W[i] = w;
            V[i] = v;
        }

        for(int i = 1; i <= n; i++) {
            for(int j = 1; j <= k; j++) {
                if(W[i] > j) {  // 무게 제한 j로 W[i]이 감당이 안 되는 경우
                    dp[i][j] = dp[i-1][j];
                }else {  // W[i]를 포함해서 새로운 조합을 만들 수 있는 경우 (= j가 W[i] 감당 가능)
                    dp[i][j] = Math.max(dp[i-1][j], dp[i-1][j-W[i]] + V[i]);
                }
            }
        }
        System.out.println(dp[n][k]);
    }
}

유명한 DP 유형 중 하나인 냅색(Knapsack) 문제라고 한다.

입력 값에 대하여 weight, value 두 개의 값이 주어지는 경우를 말한다. 냅색 안에서도 여러 가지 종류로 나눠지는데 이 경우는 0-1 Knapsack이다.

입력 값을 더 작은 단위로 나눌 수 없다는 뜻인데 내 수준에서는 그냥 0-1냅색 유형 하나만 있다고 알고 있어도 되지 않을까 싶다.

두 개의 입력 값을 어떻게 처리해야 할지, DP배열의 값을 어떻게 정의해야할지 모든 게 낯설고 어색했다.

대표적인 유형이라고 그냥 수업 듣는 느낌으로 조금만 생각해보고 바로 풀이를 확인했다.

dp[n][k] = 1~n의 물건을 가지고 무게 제한 k 안에서 채울 수 있는 최대 value 이다.

O(n * k) = 10,000,000 (천 만)으로 충분히 시간 안에 들어올 수 있다.

i 반복이 새로 돌 때마다의 의미는 이렇게 표현할 수 있다.

i-1번째 물건까지 살펴보았고 배낭의 용량이 j-w[i] 였을 때의 값에, 새롭게 i번째 물건을 넣는 상황

(j-w[i]인 상황에서 넣는 이유는? -> 그래야 i번째 물건을 넣어서 무게가 j가 될 거니까. 무게 j를 채우는 경우를 찾는 건 아니지만 j 범위 안에서 최대 밸류를 찾는 것도 이런식으로 처리할 수 있다)

아.. 너무 어렵다... ㅋㅋ