[Algorithm] 백준_평범한 배낭_12865번 (JAVA) 🎒

2025. 3. 23. 00:23·Algorithm

📝문제

https://www.acmicpc.net/problem/12865

평범한 배낭_12865번

티어: 골드 5

💡풀이

문제 유형

다이나믹 프로그래밍

 

걸린 시간

60분

 

시간 복잡도

O(NxK)

 

풀이 방법 도출

  1. 일단 dp라고 생각도 못했고, 배낭문제 유형이 있다는 것도 몰랐다.. 그래서 문제 이해하는데만 30분 걸린 거 같다
  2. 이 블로그 덕분에 겨우 풀 수 있었다.. https://howudong.tistory.com/60
import java.util.*;
import java.io.*;
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[][] dp = new int[N+1][K+1];

        for(int i = 1; i <= N; i++){
            st = new StringTokenizer(br.readLine());
            //현재 물건
            int W = Integer.parseInt(st.nextToken());//무게
            int V = Integer.parseInt(st.nextToken());//가치

            for(int j = 0 ; j <= K; j++){//j무게의 배낭
                if(j < W){//배낭에 넣을 수 있는 최대 무게 보다 물건의 무게가 클 때 => 배낭에 물건을 넣을 수 없음
                    dp[i][j] = dp[i-1][j];
                }else{//배낭에 넣을 수 있는 최대 무게 보다 물건의 무게가 작거나 같을 때 => 배낭에 물건을 넣을 수 있음
                    dp[i][j] = Math.max(dp[i-1][j], V + dp[i-1][j-W]);
                }
            }

        }
        System.out.println(dp[N][K]);
    }
}

 

🤔Review

어려웠지만 쀼듯해..

'Algorithm' 카테고리의 다른 글

[Algorithm] 백준_최소비용 구하기_1916번 (JAVA) 다익스트라  (0) 2025.03.24
[Algorithm] 백준_DNA 비밀번호_12891번 (JAVA) 슬라이딩 윈도우  (0) 2025.03.23
[Algorithm] 백준_이중 우선순위 큐_7662번 (JAVA) TreeMap  (0) 2025.03.21
[Algorithm] 백준_특정한 최단 경로_1504번 (JAVA)  (1) 2025.03.20
[Algorithm] 백준_수들의 합 5_2018번 (JAVA)  (2) 2025.03.18
'Algorithm' 카테고리의 다른 글
  • [Algorithm] 백준_최소비용 구하기_1916번 (JAVA) 다익스트라
  • [Algorithm] 백준_DNA 비밀번호_12891번 (JAVA) 슬라이딩 윈도우
  • [Algorithm] 백준_이중 우선순위 큐_7662번 (JAVA) TreeMap
  • [Algorithm] 백준_특정한 최단 경로_1504번 (JAVA)
dev_ajrqkq
dev_ajrqkq
알고리즘 천재가 될 거야
  • dev_ajrqkq
    기록이 자산이다
    dev_ajrqkq
  • 전체
    오늘
    어제
    • 분류 전체보기 (147)
      • Front-end (0)
      • Back-end (11)
        • Spring (1)
        • Java (8)
      • CS (9)
        • 데이터베이스 (5)
        • 네트워크 (4)
      • Algorithm (80)
      • 이것저것 (0)
      • 버그잡기 (1)
      • TIL (37)
      • 후기 (1)
      • 취준 (0)
  • 블로그 메뉴

    • 링크

    • 공지사항

    • 인기 글

    • 태그

      티스토리챌린지
      항해99
      99클럽
      Til
      코딩테스트준비
      TypeScript
      개발자취업
      오블완
    • 최근 댓글

    • 최근 글

    • hELLO· Designed By정상우.v4.10.2
    dev_ajrqkq
    [Algorithm] 백준_평범한 배낭_12865번 (JAVA) 🎒
    상단으로

    티스토리툴바