Baekjoon 1535 안녕 JAVA

1535번: 안녕

문제

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

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

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

입력

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

출력

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

풀이

1. 백트래킹

DFS를 이용하여 인원들을 방문하는 인원, 방문하지 않는 인원을 탐색해가면서

소모 체력이 100이 넘는다면 종료하고, 체력이 남아있다면 끝까지 탐색을 하면서, 최대로 얻을 수 있는 행복을 출력

 

2. 다이나믹 프로그래밍

배낭 알고리즘을 이용하여 특정 체력으로 얻을 수 있는 가장 큰 행복을 구하고,

연산을 반복하여 마지막까지 탐색

코드

import java.io.*;
import java.util.*;

public class Main {
	// DP
	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n=Integer.parseInt(br.readLine());
		int [] l = new int[n], g = new int[n], dp = new int[100];	// Lose, Get, DP 배열
		StringTokenizer st = new StringTokenizer(br.readLine());
		for(int i=0;i<n;i++)
			l[i]=Integer.parseInt(st.nextToken());
		st = new StringTokenizer(br.readLine());
		for(int i=0;i<n;i++)
			g[i]=Integer.parseInt(st.nextToken());
		// i : 사용 체력에 따른 최대 값
		// dp[i] : 해당 체력에서 얻을 수 있는 최대 행복값
		for(int i=0;i<n;i++) {	// 현재 있는 사람의 값으로 경우의 수를 계산
			for(int j=99;j>=l[i];j--) {	// 현재 있는 사람의 잃는 체력을 기준으로 하나씩 감소해가면서 현재 사람으로 시작하는 경우까지 탐색
				dp[j]=Math.max(dp[j], dp[j-l[i]]+g[i]);	// 현재 체력과 현재 체력에서 감소해가며 현재 사람을 이용하여 얻을 수 있는 값 중 큰 값을 저장 
			}
		}
		System.out.println(dp[99]);	// 사용 체력이 100일때는 0을 출력하기에, 99까지 밖에 출력을 하지 못함
		// 99에 저장되어있는 최대행복 값을 출력
	}
	
	/*
	백트래킹
	static int ans, n;
	static int [][] people;
	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		n=Integer.parseInt(br.readLine());
		people = new int [n][2];
		StringTokenizer st = new StringTokenizer(br.readLine());
		for(int i=0;i<n;i++)
			people[i][0]=Integer.parseInt(st.nextToken());
		st = new StringTokenizer(br.readLine());
		for(int i=0;i<n;i++)
			people[i][1]=Integer.parseInt(st.nextToken());
		dfs(0, 0, 0);
		System.out.println(ans);
	}
	static public void dfs(int s, int sumh, int sump) {
		if(sumh>=100)	// 소모 체력이 100이상이면 조건에 맞지 않기에 리턴
			return;	
		if(sump>ans)	// 얻은 행복이 ans보다 크다면 ans를 갱신
			ans=sump;
		if(s==n)	// 선택한 사람이 마지막 사람이면 리턴
			return;
		dfs(s+1,sumh+people[s][0],sump+people[s][1]);	// 현재 사람을 선택한 경우
		dfs(s+1,sumh,sump);	// 현재 사람을 선택하지 않은 경우
	}
	*/
}