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

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

1493번: 박스 채우기

입력

첫째 줄에 세 자연수 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을 출력합니다.