백준 : 박스채우기(1493) with 자바

2023. 9. 17. 16:38· 백준 : 분할정복

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

 

1493번: 박스 채우기

세준이는 length × width × height 크기의 박스를 가지고 있다. 그리고 세준이는 이 박스를 큐브를 이용해서 채우려고 한다. 큐브는 정육면체 모양이며, 한 변의 길이는 2의 제곱꼴이다. (1×1×1, 2×2×2,

www.acmicpc.net

입력

첫째 줄에 세 자연수 length width height가 주어진다.

둘째 줄에 세준이가 가지고 있는 큐브의 종류의 개수 N이 주어진다.

셋째 줄부터 총 N개의 줄에 큐브의 종류 Ai와 개수 Bi가 i가 증가하는 순서대로 주어진다. 큐브의 종류는 한 변의 길이를 나타낼 때 쓰는 2i에서 i이다.

 

예제 입출력을 살펴보자.

예제 입력 1 복사

4 4 8
3
0 10
1 10
2 1

입출력이 어떻게 나오는지 방법을 확인했으므로 바로 코드를 만들어보자.

import java.util.Scanner;

public class 박스채우기 {
      public static void main(String[] args){
            Scanner sc = new Scanner(System.in);
            int length = sc.nextInt();
            int width = sc.nextInt();
            int height = sc.nextInt();
            int N = sc.nextInt();
            int arr[] = new int[N];

            for(int i=0; i < N; i++){
                  int a = sc.nextInt();
                  int b = sc.nextInt();
                  arr[a] = b;
            }

            long use = 0;
            long count = 0;
            for( int i=N - 1; i >= 0; i--){
                   use <<= 3; //2^3
                   long partition = (long) (length >> i) * (width >> i) * (height >> i) - use;
                   long box = Math.min((long) arr[i], partition);
                   use += box;
                   count += box;
            }
            if(use == (long) length * width * height){ //계산 결과와 박스의 부피가 같은지 확인
                System.out.println(count);
            }      
            else{
                     System.out.println(-1);
            }
      }
}

먼저 스캐너, 입력받을 변수와 배열들을 생성해준다.

length = 가로

width = 세로

height = 높이

N = 입력받을 큐브의 개수

arr[] = 배열을 저장

반복문을 사용해서 i < N까지 a와 b의 값을 입력받는다.

이때 arr[a] = b가 되도록 저장한다. -> a x a x a의 개수가 b임을 나타낸다.

use 사용한 큐브의 크기를 저장

count 큐브의 총 개수를 저장

반복문을 사용하여 사용한 큐브의 개수가 몇개인지 확인합니다.

i에 n-1을 저장하고 하나씩 줄여가면서 조사할 것입니다.

use <<= 3 이것은 자바에서 2^3을 의미합니다.

이제 분할 정복을 사용하여 큐브의 개수를 계산할것입니다,

long partition =  2^i x 2^i x 2^i만큼 분할해 주고, 전에 박스를 채웠던 큐브의 개수(use)만큼 빼 준다.

box의 최솟값을 계산합니다.

사용한 큐브의 개수를 box에 저장합니다.

총개수를 박스에 더합니다.

마지막으로 계산결과와 박스의 부피가 일치하는지 확인하고 일치한다면 count(총 개수)를 출력하고

일치하지 않는다면 -1을 출력합니다.

 

저작자표시 (새창열림)

'백준 : 분할정복' 카테고리의 다른 글

백준 : 레벨 햄버거(16974) with 자바  (0) 2023.09.15
백준 : 프렉탈 평면(1030) with 자바  (0) 2023.09.15
백준 : 색종이 만들기(2630) with 자바  (0) 2023.09.12
백준 : 행렬 제곱(10830) with 자바  (0) 2023.09.12
'백준 : 분할정복' 카테고리의 다른 글
  • 백준 : 레벨 햄버거(16974) with 자바
  • 백준 : 프렉탈 평면(1030) with 자바
  • 백준 : 색종이 만들기(2630) with 자바
  • 백준 : 행렬 제곱(10830) with 자바
유민기
유민기
유민기
Youminki
유민기
전체
오늘
어제
  • 분류 전체보기 (45)
    • 백준 : BFS (5)
    • 알고리즘(이충기 교수) (4)
    • 웹해킹 (6)
    • 백준 : 동적 프로그래밍 (11)
    • 백준 : 분할정복 (5)
    • 백준 : backtraking (2)
    • 컴퓨터 보안(한승철 교수) (4)
    • FrontEnd (4)

블로그 메뉴

  • 홈
  • 태그
  • 방명록

공지사항

인기 글

태그

최근 댓글

최근 글

hELLO · Designed By 정상우.v4.2.0
유민기
백준 : 박스채우기(1493) with 자바
상단으로

티스토리툴바

단축키

내 블로그

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

블로그 게시글

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

모든 영역

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

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