[문제풀이] 10-06. 최대 점수 구하기

인프런, 자바(Java) 알고리즘 문제풀이

Dynamic Programming - 1006. 최대 점수 구하기(냅색 알고리즘)

🗒️ 문제

🎈 나의 풀이

	private static class Problem {
        int s, t;

        public Problem(int s, int t) {
            this.s = s;
            this.t = t;
        }
    }
    private static int solution(int n, int limit, List<Problem> list) {
        int[] dy = new int[limit + 1];

        for(int i=list.get(0).t; i<=limit; i++) {
            dy[i] = list.get(0).s;
        }

        for(int i=1; i<n; i++) {
            Problem p = list.get(i);

            for(int j=limit; j>=p.t; j--) {
                if(dy[j] < dy[j - p.t] + p.s) {
                    dy[j] = dy[j - p.t] + p.s;
                }
            }
        }

        return Arrays.stream(dy).max().getAsInt();
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int limit = sc.nextInt();
        List<Problem> list = new ArrayList<>();

        for(int i=0; i<n; i++) list.add(new Problem(sc.nextInt(), sc.nextInt()));

        System.out.println(solution(n, limit, list));
    }

🖍️ 강의 풀이

  class Main{
      public static void main(String[] args){
          Scanner kb = new Scanner(System.in);
          int n=kb.nextInt();
          int m=kb.nextInt();
          int[] dy=new int[m+1];
          for(int i=0; i<n; i++){
              int ps=kb.nextInt();
              int pt=kb.nextInt();
              for(int j=m; j>=pt; j--){
                  dy[j]=Math.max(dy[j], dy[j-pt]+ps);
              }
          }
          System.out.print(dy[m]);
      }
  }

💬 짚어가기

해당 문제는 그래프의 Dynamic Programming(동적 계획법)을 통해 풀 수 있다.
그 중 냅색(knapsack) 알고리즘을 이용하여 풀이하였다.

이전에 풀이한 동전 교환 문제와 동일한 로직이다. 한 가지 추가된 점은 이번 문제에서는
사용할 수 있는 각 유형의 횟수가 1번으로 제한된다.

주어진 제한 시간을 의미하는 배열 dy를 생성하고, 해당 배열의 뒤에서 부터 접근한다.
( 문제의 풀이 시간만큼 앞에 존재하는 배열 요소에 접근하여 점수를 더하는 방식으로
앞에서부터 접근하게 되면 같은 문제를 중복으로 체크하게 된다. )