[Java] 1535. 안녕

문제

세준이는 성형수술을 한 후에 병원에 너무 오래 입원해 있었다. 이제 세준이가 병원에 입원한 동안 자기를 생각해준 사람들에게 감사하다고 말할 차례이다.

세준이를 생각해준 사람은 총 N명이 있다. 사람의 번호는 1번부터 N번까지 있다. 세준이가 i번 사람에게 인사를 하면 L[i]만큼의 체력을 잃고, J[i]만큼의 기쁨을 얻는다. 세준이는 각각의 사람에게 최대 1번만 말할 수 있다.

세준이의 목표는 주어진 체력내에서 최대한의 기쁨을 느끼는 것이다. 세준이의 체력은 100이고, 기쁨은 0이다. 만약 세준이의 체력이 0이나 음수가 되면, 죽어서 아무런 기쁨을 못 느낀 것이 된다. 세준이가 얻을 수 있는 최대 기쁨을 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 사람의 수 N(<=20)이 들어온다. 둘째 줄에는 각각의 사람에게 인사를 할 때, 잃는 체력이 1번 사람부터 순서대로 들어오고, 셋째 줄에는 각각의 사람에게 인사를 할 때, 얻는 기쁨이 1번 사람부터 순서대로 들어온다. 체력과 기쁨은 100보다 작거나 같은 자연수 또는 0이다.

출력

첫째 줄에 세준이가 얻을 수 있는 최대 기쁨을 출력한다.

예제 입력 1 

3

1 21 79

20 30 25

예제 출력 1 

50

 

 

🐝 나의 풀이

import java.io.*;

public class Main{
   static BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
   static int[][] dp;
   static int N;
   static int[] hp;
   static int[] joy;

   public static void main(String[] args) throws Exception{
       N=Integer.parseInt(br.readLine());   // 사람의 수
       hp=new int[N+1];
       joy=new int[N+1];
       dp=new int[N+1][101];
       input(hp);
       input(joy);
       search();
       System.out.println(dp[N][99]);

   }

   public static void search(){
       for(int i=1; i<=N; i++){
           for(int j=1; j<=100; j++){
               if(j >= hp[i]){
                   dp[i][j]=Math.max(dp[i-1][j], dp[i-1][j-hp[i]]+joy[i]);
               }else{
                   dp[i][j]=dp[i-1][j];
               }
           }
       }
   }

   public static void input(int[] arr) throws Exception{
       arr[0]=0;
       int i=1;
       for(String s : br.readLine().split(" ")){
           arr[i]=Integer.parseInt(s);
           i++;
       }
   }
}

dp로 풀었다. 배낭문제를 공부한 뒤에 풀었다.

배낭문제에 비유를 하면 체력=무게, 기쁨=가치다.

i 이전의 기쁨, i에게 인사한 후 기쁨 중 더 큰 값을 dp에 넣는다.

j가 hp[i]보다 작으면 i 이전의 기쁨을 넣는다.

 

 

# 실패
N=int(input())      # 사람의 수
health=list(map(int, input().split()))    # 잃는 체력
joy=list(map(int, input().split()))       # 얻을 수 있는 최대 기쁨
answer=0
body=100
info=list()

for i in range(N) :
    info.append([joy[i], health[i]])
info.sort(reverse=True)

for i in range(N) :
    if body-info[i][1] > 0 :
        body-=info[i][1]
        answer+=info[i][0]

print(answer)

문제에 테케 1개만 통과하고 제출하니 실패

기쁨이 큰 순으로 정렬 후 body-info[i][1]가 0보다 큰 기쁨을 answer에 더해간다.

이 방법의 문제점은 기쁨이 큰 순으로 더했다고 최대 기쁨을 만들 수 있다는 보장이 없는 것이다..

완탐을 해야한다.

 

 

👻 다른 사람 풀이

 

# https://sangminlog.tistory.com/entry/boj-1535
N=int(input())
L=[int(x) for x in input().split()]		# 체력
J=[int(x) for x in input().split()]		# 기쁨
L, J=[0]+L, [0]+J
dp=[[0 for _ in range(101)] for _ in range(N+1)]

for i in range(1, N+1) :
    for j in range(1, 101) :
        if L[i] <= j :	# i에게 인사할 만큼의 체력이 있으면
            dp[i][j]=max(dp[i-1][j], dp[i-1][j-L[i]]+J[i])
        else :
            dp[i][j]=dp[i-1][j]

print(dp[N][99])

dp로 구현

 

 

// https://mygumi.tistory.com/203
import java.util.Scanner;

public class Main{
    static boolean[] visited;
    static int[] hp=new int[21];
    static int[] up=new int[21];
    static int n, ans;

    public static void main(String[] args){
        Scanner sc=new Scanner(System.in);
        n=sc.nextInt();
        for(int i=1; i<=n; i++){
            hp[i]=sc.nextInt();
        }

        for(int i=1; i<=n; i++){
            up[i]=sc.nextInt();
        }

        for(int i=1; i<=n; i++){
            for(int j=1; j<=n; j++){
                visited=new boolean[21];
                dfs(100-hp[j], up[j], j, 1, i);
            }
        }
        System.out.println(ans);
    }
    
	// 체력, 기쁨, 시작 인덱스, 현재 인덱스, 끝 인덱스
    public static void dfs(int life, int happy, int v, int cnt, int shakeN){
        if(cnt == shakeN){
            if(life>0){	// 체력이 0보다 크면 살아있음
                ans=Math.max(ans, happy);
            }
        }else{	// v에서 shakeN까지 계산할 때까지
            for(int i=v+1; i<=n; i++){
                if(!visited[i]){
                    visited[i]=true;
                    dfs(life-hp[i], happy+up[i], i, cnt+1, shakeN);
                }
            }
        }
        visited[v]=false;
    }
}

 

백트래킹 풀이

j부터 i까지 백트래킹으로 최대 기쁨을 계산한다.

입력의 길이가 3이라면 (1, 1), (2, 1), (3, 1), (2, 2), (2, 3), (3, 3)의 범위에서 계산한다.

모든 범위를 다 계산해보는 것이다.

cnt가 shakeN과 같으면 계산하려던 범위까지 다 계산한 것이다.

 

 

// https://mygumi.tistory.com/203
import java.util.Scanner;

public class Main{
    static int[] hp=new int[21];
    static int[] up=new int[21];
    static int[][] dp=new int[21][101];

    public static void main(String[] args){
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        int ans=0;

        for(int i=1; i<=n; i++){
            hp[i]=sc.nextInt();
        }

        for(int i=1; i<=n; i++){
            up[i]=sc.nextInt();
        }

        dp[1][100-hp[1]]=up[1];

        for(int i=2; i<=n; i++){
            dp[i][100-hp[i]]=up[i];
            for(int j=100; j>0; j--){
                if(j+hp[i] <= 100 && dp[i-1][j+hp[i]] != 0){
                    dp[i][j]=Math.max(dp[i-1][j+hp[i]]+up[i], dp[i-1][j]);
                }else{
                    dp[i][j]=Math.max(dp[i][j], dp[i-1][j]);
                }
            }
        }
        for(int i=100; i>0; i--){
            ans=Math.max(dp[n][i], ans);
        }
        System.out.println(ans);
    }
}

dp로 푼 풀이

dp[i][j]는 i번째 사람까지 인사하고 남은 체력이 j일 때 최대 기쁨이다.

j+hp[i]는 이전 체력+i에게 인사할 때 필요한 체력이다.

두 번째 for문 전에 dp[i][100-hp[i]]=up[i] 때문에 dp[i][j]=Math.max(dp[i][j], dp[i-1][j])다.

dp를 제대로 이해하면 위에 백트래킹 풀이보다 구현하는 게 더 쉬운 것 같다.

 

 

 

문제 출처 👉 백준