생각정리하기

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

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 ( 즉, 캐리어의 용량 ) 내에서 최대 절박도를 구하는 문제다. 

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

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

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

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

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

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

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

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

아래 식을 추가해준다. 

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

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

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;

}

}

}

n    data anwer

4    [[0,0],[1,1],[0,2],[2,0]]    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]);

}

}

answer값 출력

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;

}

}