https://algospot.com/judge/problem/read/PACKING#


문제 :


여행을 떠나기 전날까지 절대 짐을 싸지 않는 버릇이 있는 재훈이는 오늘도 비행기 타기 전날에야 가방을 싸기 위해 자리에 앉았습니다. 비행기 규정상 재훈이는 캐리어를 하나만 가지고 갈 수 있는데, 아무래도 가져가고 싶은 물건들이 캐리어 안에 다 들어가지 않을 것 같습니다. 재훈이는 가져가고 싶은 각 물건들의 부피와 얼마나 필요한지를 나타내는 절박도를 조사해 다음과 같은 목록을 만들었습니다. 


물건노트북 컴퓨터카메라XBOX365커피그라인더아령백과사전
부피4264210
절박도7106754
캐리어의 용량이 정해져 있기 때문에 가져갈 수 있는 물건들의 부피 합은 캐리어의 용량 w 이하여야 합니다. 이때 절박도를 최대화할 수 있는 물건들의 목록을 계산하는 프로그램을 작성하세요.

입력

입력의 첫 줄에는 테스트 케이스의 수 C (1≤C≤50)가 주어집니다. 각 테스트 케이스의 첫 줄에는 가져가고 싶은 물건의 수 N (1≤N≤100)과 캐리어의 용량 W (1≤W≤1000)가 주어집니다. 그 이후 N줄에 순서대로 각 물건의 정보가 주어집니다. 한 물건에 대한 정보는 물건의 이름, 부피, 절박도 순서대로 주어지며, 이름은 공백 없는 알파벳 대소문자 1글자 이상 20글자 이하의 문자열, 부피와 절박도는 1000 이하의 자연수입니다.

출력

각 테스트 케이스별 출력의 첫 줄에는 가져갈 수 있는 물건들의 최대 절박도 합과 가져갈 물건들의 개수를 출력합니다. 이후 한 줄에 하나씩 각 물건들의 이름을 출력합니다. 만약 절박도를 최대화하는 물건들의 조합이 여럿일 경우 아무 것이나 출력해도 좋습니다.


예제 입력

2
6 10
laptop 4 7
camera 2 10
xbox 6 6
grinder 4 7
dumbell 2 5
encyclopedia 10 4
6 17
laptop 4 7
camera 2 10
xbox 6 6
grinder 4 7
dumbell 2 5
encyclopedia 10 4

예제 출력

24 3
laptop
camera
grinder
30 4
laptop
camera
xbox
grinder



풀이 :


이 문제는 DP(Dynamic Programming) 문제로 유명하다는 Knapsack문제의 변형문제라고 한다. 


이 문제는 다르게 표현하면, 정해진 weight ( 즉, 캐리어의 용량 ) 내에서 최대 절박도를 구하는 문제다. 


구해야 하는 출력값에는 절박도, 물건 개수, 물건 이름이 있다. 


먼저 최대 절박도를 구해보자 .


간단 표현 식 :


findMaxHope ( 물건 리스트, 남은 캐리어 용량, 현재 아이템 ){

        # 기저부분

1. 현재 아이템이 마지막 아이템이면 나간다

2. 남은 용량이 0보다 같거나 작음 나간다.

# 현재 아이템에 포인트 1 해줌으로서, 지금 아이템을 선택 했을 절박도를 구한다

현재 아이템을 선택 할때 절박도 = findMaxHope ( 물건 리스트, 캐리어 용량, 현재 아이템 + 1) 


# 현재 아이템을 선택했을 절박도 ( 현재 아이템의 무게가, 남은 캐리어 용량보다 작아야된다 )

현재 아이템을 선택 할때 절박도  = findMaxHope ( 물건 리스트, 캐리어 용량 - 현재 아이템 무게 , 현재 아이템 + 1) 

        # 둘 중 큰 값 반환

return max ( 현재 아이템을 선택 할때 절박도, 현재 아이템을 선택 할때 절박도


}

 


식으로 간단히 표현해봤다. 

DP에서 가장 중요한 부분은 개인적인 의견으로 기저부분이라고 생각한다.. 

먼저 기저부분을 작성해준다. 


다음 논리적인 식을 적어주면된다. 현재 아이템을 선택 안 할때와 했을 때 절박도 중 최대값을 구해서 return해주면 절박도의 최대값을 구할 수 있다. 


But. 우리가 원하는 출력값에는 물건개수와 물건이름도 알아야한다. 

위의 식만 이용해선 물건개수와 물건이름을 알 수없다. 


아래 식을 추가해준다. 



getItemList ( 물건 리스트남은 캐리어 용량현재 아이템 , 아이템리스트 ){

      # 기저부분

      1. 현재 아이템이 마지막 아이템이면 나간다

      2. 남은 용량이 0보다 같거나 작음 나간다.

      

      # 두 값을 비교, 같다면 현재 아이템을 선택 안한 것이다. ( 현재 아이템을 선택 안 했기에, 절박도가 동일 ). 

      if ( findMaxHope ( 물건 리스트캐리어 용량현재 아이템 )  ==  findMaxHope ( 물건 리스트캐리어 용량현재 아이템 + 1)  )

      # 다음 포인트로 넘겨줌 

               getItemList ( 물건 리스트남은 캐리어 용량현재 아이템 + 1 , 아이템리스트 );

      else        

      # 현재 아이템까지 최대 절박도를 합친결과와 다음 아이템까지 최대 절박도를 합친 결과와 다르다면 현재 아이템은 선택된것이다. 

      # 선택 됐으니, 아이템 리스트에 추가하고, 무게를 빼서 다시 실행 

      ( 이 부분이 이해안간다면 , 위의 findMaxHope을 디버깅해가며 다시 본후 보면 이해가 빠를 것이다 ) 

              아이템리스트.add ( 현재 아이템 )

              getItemList ( 물건 리스트남은 캐리어 용량 - 현재 아이템 무게 현재 아이템 + 1 , 아이템리스트 );


}

 



이렇게 물건개수와 물건이름 또한 구할 수 있다. 


* 출처 : getItemList부분은 "알고리즘 문제해결 전략" 책을 참고하여 풀었습니다. 


 



쉽게 설명하기위해 한글로 적었는데 더 복잡한 느낌 ..

전체 코드를 보면 위에 그대로 코드로 표현하였다. 

추가된 부분 : cache 부분 추가 -- 이 부분이 없으면 timeout발생 

( dp를 이용할 때 memo기능을 이용해서 dp에서 실행된 결과는 cache처럼 저장하고 있다가 불러오면 시간단축을 할 수 있다 ) 



전체코드 

import java.util.ArrayList;

import java.util.List;

import java.util.Scanner;


public class Packing {


static int cache[][]  = new int[1001][100];

public static void main(String[] args) {

Scanner scanner = new Scanner(System.in);

int c = scanner.nextInt();

List<String> items = null;

for ( int i = 0 ; i < c ; i++) {

int n = scanner.nextInt();

int w = scanner.nextInt();


List<Stuff> stuffs = new ArrayList<Stuff>();

items = new ArrayList<String>();

for ( int j = 0 ; j < n ; j ++  ) {

String name = scanner.next();

int weight = scanner.nextInt();

int hope = scanner.nextInt();

Stuff stuff = new Stuff(name, weight, hope);

stuffs.add(stuff);

}

for (int j = 0; j < 1001 ; j++) {

for(int k = 0; k < 100 ; k++) {

cache[j][k] = -1;

}

}

int point = 0;

int hope = findMaxHope(stuffs, w, point);;

getItemList(stuffs, w, point, items );

System.out.println(hope + " "+items.size());

for ( int j = 0 ; j < items.size() ; j++ ) {

System.out.println(items.get(j));

}


}

}

private static void getItemList(List<Stuff> stuffs, int w, int point, List<String> items )

{

if( point == stuffs.size() ) {

return;

}

if( w <= 0 ) {

return;

}

// 값이 다르다면  , 최대 절박도를 얻을 있다

    if (findMaxHope(stuffs, w, point) == findMaxHope(stuffs, w, point+1))

    getItemList(stuffs, w, point + 1, items);

    else

    {

    items.add(stuffs.get(point).getName());

    getItemList(stuffs, w - stuffs.get(point).getWeight() , point + 1, items);

    }

}

private static int findMaxHope(List<Stuff> stuffs, int w, int point) {

// 기저부분 

if( point == stuffs.size() ) {

return 0;

}

if( w <= 0 ) {

return 0;

}

if( cache[w][point] != -1) {

return cache[w][point];

}

// hope 절박도 

int hope = 0;

// 현재 아이템을 선택하지 않는 경우 ( 무게가 무거워 베낭에 담을 없을 )

hope = findMaxHope(stuffs, w, point+1);

// 현재 아이템을 선택할 경우 

if( w >= stuffs.get(point).getWeight() )

{

int rhope = ( findMaxHope(stuffs, w - stuffs.get(point).weight , point+1) ) + stuffs.get(point).hope ;

if( rhope > hope ) {

hope = rhope;

}

}

cache[w][point] = hope;

return hope;

}



static class Stuff {

String name;

int weight;

int hope;


public Stuff(String name, int weight, int hope) {

this.name = name;

this.weight = weight;

this.hope = hope;

}

public String getName() {

return name;

}

public void setName(String name) {

this.name = name;

}

public int getWeight() {

return weight;

}

public void setWeight(int weight) {

this.weight = weight;

}

public int getHope() {

return hope;

}

public void setHope(int hope) {

this.hope = hope;

}

}

}

 




'algolism' 카테고리의 다른 글

[카카오예선문제]캠핑풀이설명  (0) 2018.02.24
[알골스팟] XHAENEUNG문제  (0) 2018.02.16




문제 

https://programmers.co.kr/learn/courses/30/lessons/1833


무지를 돌보느라 지친 콘은 한적한 시골의 한 캠핑장에 놀러 갔다. 캠핑장은 텐트를 칠 수 있는 넓은 평지를 제공하고 있는데, 이 평지에는 이미 캠핑장에서 설치해 놓은 n개의 쐐기가 박혀 있다. 캠핑장 이용 고객은 이 쐐기들 중 한 쌍을 골라 다음과 같은 조건을 만족하도록 텐트를 설치해야 한다.

텐트는 직사각형 형태여야 한다. 

텐트의 네 면이 정확하게 동, 서, 남, 북을 향해야 한다.

대각에 위치하는 텐트의 두 꼭짓점이 정확하게 선택한 두 개의 쐐기에 위치해야 한다.

텐트가 점유하는 직사각형 영역의 넓이는 0보다는 커야 한다.

텐트가 점유하는 직사각형 영역 내부에 다른 쐐기를 포함하면 안 된다. (다른 쐐기가 경계에 위치하는 경우는 허용함)

캠핑장에서는 위와 같은 조건을 만족하는 위치라면 어디든 고객이 텐트를 설치할 수 있도록 정확한 크기의 텐트를 모두 구비하여 대여해준다고 한다.

당신은 위와 같은 조건을 만족하는 텐트를 설치할 수 있는 쐐기의 쌍의 개수는 총 몇 가지가 될지 궁금해졌다.

n개의 쐐기의 위치가 좌표로 주어질 때, 위의 조건을 만족하는 쐐기의 쌍의 개수를 계산하는 프로그램을 작성하시오. 단, 동서 방향은 x축, 남북 방향은 y축과 평행하다고 가정한다. 



입력형식

입력은 쐐기의 개수를 의미하는 정수 n과, n × 2 크기의 2차원 배열 data로 주어지며, 배열의 각 행은 캠핑장에 설치된 쐐기의 x좌표와 y좌표를 의미한다. 제한 조건은 다음과 같다.


2 <= n <= 5,000

n개의 쐐기는 모두 x좌표 0 이상 2^31-1 이하, y좌표 0 이상 2^31-1 이하에 위치한다.

입력되는 n개의 쐐기 중 x좌표와 y좌표가 모두 같은 경우는 없다. 



출력형식

 입력에 주어진 각 케이스에 대해 가능한 텐트의 쐐기의 쌍의 개수를 정수 형태로 리턴한다.


예제 입출력

n    data anwer

4    [[0,0],[1,1],[0,2],[2,0]]    3




이 문제를 풀려면 O(n^3)으론 풀수 없다고한다. 최적화를 해서 푼사람도 있다는 ... 

참고 : http://tech.kakao.com/2017/08/11/code-festival-round-1/



그럼 O(n^2)로 풀어야 한다는 건데 아래와 같은 일반 방식으론 풀수없다.


일반방식 ( 가장 간단히 생각할 수 있는 방식 )  : 

모든 쐐기를 검사하며 확인하는 방법이다.

이방법의 경우 정한 두 쐐기 안에 다른 쐐기가 있는지 확인하기 위해 for문을 한번 더 돈다.

총 n의 크기가 5천개니까 5000^3까지 돌수 있기 때문에, 이 경우 실패한다.


int n;


// x,y포인트을 저장 변수

int data[n][2];


for ( int I = 0 ; I < n ; I++) {

      data[I][0] = x좌표;

      data[I][1] = y좌표;

}

// 첫번째 쐐기

for (  I = 0 ; I < 쐐기의 수 - 1 ; I++) {

// 두번째 쐐기

for ( j = I+1 ; j < 쐐기의 수 : j++ ) {


// 두 쐐기가 같은 행이나 열에 있는 경우 제외 

       if(data[i][0] == data[j][0] || data[i][1] == data[j][1] )

      {

        continue;

      }

      // 두 쐐기를 통해 사각형을 만들었을 때, 각 좌표값들을 저장

int endX = Math.max(data[j][0], data[i][0]);

int startX = Math.min(data[j][0], data[i][0]);

int endY = Math.max(data[j][1], data[i][1]);

int startY = Math.min(data[j][1], data[i][1]);


boolean value = true;

// 모든 쐐기를 검사하며 공간안에 쐐기가 박혀있는지 확인 

for ( k = 0 ; k < data.length ; k++ ) {

        if( startY < data[k][1] && data[k][1] < endY && startX <= data[k][0] && data[k][0] <= endX ) {

value = false;

break;

       }

}

if( value ) {


answer ++;

}

}


}


answer값 출력



결국 이 문제를 풀기 위해서는 좌표 압축과, 부분 합 배열을 알아야한다. 


필자의 경우 부분 합 배열을 아래 사이트를 보고 이해했다.

참고 : http://meansoup.blogspot.kr/2017/09/blog-post.html


먼저 좌표 압축이란 무엇인가 ....

말 그대로 좌표를 압축시키는 거다 .

예) (1 , 40) , ( 2, 7 ), ( 10, 20 )  --> (1,3) , (2,1) , (3, 2) 
이 와같은 좌표들이 있다면, 값 들의 크기는 이 문제에서 중요하지 않다. 오직 순서만 중요하다.

 

 



이 그림들이 여기 문제에서는 같은 의미라는 것을 알 수있다.

그럼 좌표 압축을 시켜준 후에, 부분 합 배열을 통해 내부에 쐐기가 있는 지 검사해야한다. 

부분 합배열 

 1

 1

  0 

  0

 0 

 0

  1

  0

 0

 1

  0

  1

 1

 0

  0

  1

위 그림은 x,y좌표의 쐐기 위치


 1

 2

 2

 2

 1

 2 

 3

 3

 1

 3

 4

 5

 2

 4

 5

 7

위 그림은 쐐기를 부분 합해서 구한 그림



그럼 부분합을 어떻게 이용하는지 보자 

첫번 째 방법에서는 내부에서 모든 쐐기를 검사하였다. 

여기서 두번 째 방법에서는 

1. 행이나 열이 하나만 차이나면 무조건 텐트를 칠 수 있기에 합을 해준다.

2. 그게 아닐 시, 부분합을 이용 쐐기를 검사해준다. 



2번의 경우를 설명하겠다. 

위에 주황색 사각형의 숫자 5는 3행 3열까지의 모든 쐐기를 더 한 경우다.  

위의 파랑색은 2번째 행의 모든 쐐기를 더한 경우이고 초록색은 2번째 열의 쐐기를 모두 더한 경우라고 생각하면된다.

그리고 핑크색은 2행 2열까지의 모든 쐐기를 더한 경우다.


그럼 예로서 (2,2)에서 (3,3)까지 텐트를 칠때, 안에 쐐기를 어떻게 검사하냐 ( 물론 행,열이 하나 차이나기에 무조건 텐트를 칠수있지만 예를 쉽게하기 위해 이런 예를 들었습니다 ). 

주황색 사각형에서 초록색 사각형과 파랑색사각형을 빼주고 핑크색이 중복으로 빼졌으니 핑크색 사각형을 더 해주면 해당 좌표안에 쐐기를 확인할 수있다. 

( 주황색 사각형 - ( 초록색 사각형 + 파랑색 사각형 ) + 핑크색 사각형 ) = ( 5 - ( 3  +  4)  + 3 )  

이 값이 0이 아닐 시 쐐기가 추가된거라고 보면된다.



이와 같은 방식으로 풀면 O(n^2) 으로 풀 수 있다.

아래는 문제를 풀때 도저히 답이 안나와서 참고한 링크..


코드 : 

http://stack07142.tistory.com/289





'algolism' 카테고리의 다른 글

[알골스팟] PACKING 문제  (0) 2018.03.03
[알골스팟] XHAENEUNG문제  (0) 2018.02.16

문제 

https://algospot.com/judge/problem/read/XHAENEUNG

위 사이트를 들어가서 확인


문자로 입력받은 숫자들의 연산을 하여, 결과값으로 출력해주는 문제였다.


주의할점 

연산을 하였을 때, 결과값이 10을 넘거나 0보다 작을 시 정답이 아닌걸로 간주한다.


문제가 비교적 쉬운 문제라, 위의 주의할점만 제대로 지키면 해결할 수 있을거라 생각합니다. 


푼방법 

문자를 숫자값으로 변환하여, 연산을 처리한다.

처리한 결과값을 다시 문자열값으로 변환하여, 제공된 결과값과 비교한다. 

비교 시 two * five = svene 이런식으로 알파벳 개수가 같을 시에도 정답으로 인정해줘야한다.

한 문자씩 비교하여, 정답으로 제공된 결과값에서 빼주는 식으로 처리하였다. 


코드 

package com.yjh.algol;

import java.util.Scanner;

public class XHAENEUNG {

static String num[] = { "zero", "one", "two", "three", "four", "five", "six", "seven","eight","nine", "ten" };

public static void main(String[] args) {

Scanner scanner = new Scanner(System.in);

int n = scanner.nextInt();

int fNum = 0;

int lNum = 0;

String oper ;

String sresult;

int result = -1;

for ( int i = 0 ; i < n ; i++ ) {

// 숫자들의 입력을 받아올 때, 위에 num[]에 저장 된 문자열과 비교하여 숫자값으로 바꿔준다.

fNum = findNum( scanner.next() );

oper = scanner.next();

lNum = findNum( scanner.next() );

scanner.next();

sresult = scanner.next();


// 받은 두 숫자값을 이용, 결과값을 출력해준다.

if( oper.equals("+")) {

result = fNum + lNum;

} else if ( oper.equals("-") ) {

result = fNum - lNum;

} else if ( oper.equals("*") ) {

result = fNum * lNum;

}

// 예외 처리) 숫자가 10보다 크거나, 0보다 작음 잘 못된 값으로 간주한다. 

if( result >  10 || result < 0 ) {

System.out.println("No");

continue;

}


                        // 연산을 한 숫자 문자열 값과, 결과값으로 제공된 값을 비교한다.

                        // 길이가 같다면 한 글자씩 없애준다.

                        // 결과로서 모든 문자열이 제거 됐다면 성공, 아닐 시 실패 

int length = sresult.length();

int nlength = num[result].length();

String temp;

boolean tfalse = true;

if( length != nlength ) {

tfalse = false;

}else { 

temp = num[result];

for (int j = 0 ; j < length ; j++) {

temp = temp.replaceFirst(sresult.charAt(j)+"", "");

}

if(temp.length() > 0) {

tfalse = false;

}

}

if(tfalse) {

System.out.println("Yes");

} else {

System.out.println("No");

}

}

}

static int findNum(String number) { 

int index = -1;

for( int i =0 ; i < num.length ; i++) {

if( number.equals(num[i])) {

index = i;

break;

}

}

return index;

}

}


 











'algolism' 카테고리의 다른 글

[알골스팟] PACKING 문제  (0) 2018.03.03
[카카오예선문제]캠핑풀이설명  (0) 2018.02.24

+ Recent posts