[JAVA] 백준 1106번 : 호텔

2024. 5. 15. 14:42·Algorithm/Beakjoon
목차
  1. 💡 DP
  2. 풀이
반응형

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


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

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int C = Integer.parseInt(st.nextToken());
        int N = Integer.parseInt(st.nextToken());
        int[] cost = new int[N];
        int[] cnt = new int[N];
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            cost[i] = Integer.parseInt(st.nextToken());
            cnt[i] = Integer.parseInt(st.nextToken());
        }

        int[] dp = new int[C + 100];
        Arrays.fill(dp, Integer.MAX_VALUE);
        dp[0] = 0;

        for (int i = 0; i < N; i++) {
            for (int j = 0; j < dp.length; j++) {
                if(dp[j] == Integer.MAX_VALUE) continue;
                int tmp = j + cnt[i];
                if(tmp < C + 100)
                    dp[tmp] = Math.min(dp[tmp], dp[j] + cost[i]);
            }
        }
        int ans = Integer.MAX_VALUE;
        for (int i = C; i < C+100; i++) {
            ans = Math.min(ans, dp[i]);
        }

        System.out.println(ans);
    }
}

💡 DP

풀이

  • p원을 들어서 c명의 고객을 불러들이는 구조, 이때 정수배도 가능하다
  • 결국 c의 가치를 가지고 무게가 p인 짐을 넣는 가방문제와 동일한 구조 (이때 물건은 무한개 가능)
    • 가치가 C 이상인 경우의 수 중 최소 무게를 가지는 경우를 출력하는 방식
dp[c] = p : c명의 고객을 확보하기 위한 최소 비용 p

 

- 이때 dp 범위를 결정하는게 중요하다. 범위를 0 ~ C+100으로 설정해준다.

   - 최악의 경우를 생각해보자, 현재까지 dp[C-1]이 최선인 상황이다. 이때 설상가상 (100명, 비용 1원)이 존재하는 상황이다. 

   -> 이 경우 100명을 플러스 한다고 쳐도 인원의 최대값은 c + 99다. 즉 c + 100 이상의 범위는 고려할 필요가 없다는 것

- dp를 MAX_VALUE로 초기화 해준다 (min 연산을 사용해야 하므로), dp[0]은 0으로 초기화

 

- 모든 경우 (p, c)에 대해서 dp에 대해 0 ~ C + 100 까지 for문 돌림, j에 대해 dp[j + c] 값을 dp[j] + p로 갱신

    - dp[j] = MAX인 경우 : 해당 경우 j명을 확보하는 것은 (p, c)로는 불가능하므로 pass

    - j + c < C + 100 인 경우에만 진행 : 기존 값과 새로운 값 (dp[j] + p) 중 작은 값으로 갱신

 

반응형

'Algorithm > Beakjoon' 카테고리의 다른 글

[JAVA] 백준 17281번 : ⚾  (0) 2024.05.17
[JAVA] 백준 17135번 : 캐슬 디펜스  (0) 2024.05.17
[JAVA] 백준 9084번 : 동전  (0) 2024.05.13
[JAVA] 백준 14567번 : 선수과목 (Prerequisite)  (0) 2024.05.12
[JAVA] 백준 3649번 : 로봇 프로젝트  (0) 2024.05.12
  1. 💡 DP
  2. 풀이
'Algorithm/Beakjoon' 카테고리의 다른 글
  • [JAVA] 백준 17281번 : ⚾
  • [JAVA] 백준 17135번 : 캐슬 디펜스
  • [JAVA] 백준 9084번 : 동전
  • [JAVA] 백준 14567번 : 선수과목 (Prerequisite)
mopipi
mopipi
칠전팔기
mopipi
공부하는 사람
mopipi
전체
오늘
어제
  • 분류 전체보기 (162)
    • Java (4)
    • Spring (21)
      • Spring boot 입문 (16)
      • [dsc] Spring-Novice-Study (3)
    • SQL (5)
    • Algorithm (127)
      • Programmars (38)
      • Beakjoon (85)
    • Git (1)
    • 생각들 (0)

블로그 메뉴

  • 홈
  • 태그
  • 방명록

공지사항

hELLO· Designed By정상우.v4.5.2
mopipi
[JAVA] 백준 1106번 : 호텔

개인정보

  • 티스토리 홈
  • 포럼
  • 로그인
상단으로

티스토리툴바

단축키

내 블로그

내 블로그 - 관리자 홈 전환
Q
Q
새 글 쓰기
W
W

블로그 게시글

글 수정 (권한 있는 경우)
E
E
댓글 영역으로 이동
C
C

모든 영역

이 페이지의 URL 복사
S
S
맨 위로 이동
T
T
티스토리 홈 이동
H
H
단축키 안내
Shift + /
⇧ + /

* 단축키는 한글/영문 대소문자로 이용 가능하며, 티스토리 기본 도메인에서만 동작합니다.