[BOJ/JAVA] 백준 1535 : 안녕 (자바)

문제 정보

  문제명   - 안녕
  난이도   - 실버 II
문제 번호 - 1535번

---

문제 링크

BOJ_S2_1535_안녕

1535번: 안녕

---

문제

세준이는 성형수술을 한 후에 병원에 너무 오래 입원해 있었다. 이제 세준이가 병원에 입원한 동안 자기를 생각해준 사람들에게 감사하다고 말할 차례이다.
세준이를 생각해준 사람은 총 N명이 있다. 사람의 번호는 1번부터 N번까지 있다. 세준이가 i번 사람에게 인사를 하면 L[i]만큼의 체력을 잃고, J[i]만큼의 기쁨을 얻는다. 세준이는 각각의 사람에게 최대 1번만 말할 수 있다.
세준이의 목표는 주어진 체력내에서 최대한의 기쁨을 느끼는 것이다. 세준이의 체력은 100이고, 기쁨은 0이다. 만약 세준이의 체력이 0이나 음수가 되면, 죽어서 아무런 기쁨을 못 느낀 것이 된다. 세준이가 얻을 수 있는 최대 기쁨을 출력하는 프로그램을 작성하시오.

---

입력

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

---

출력

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

---

예제 입력/출력

예제 입력	예제 출력
3 1 21 79 20 30 25	50
1 100 20	0
8 100 15 1 2 3 4 6 5 49 40 1 2 3 4 5 4	59
4 100 50 20 13 20 30 40 50	120
8 100 26 13 17 24 33 100 99 34 56 21 1 24 34 100 99	135
12 1 1 1 1 1 1 1 1 1 1 1 1 100 100 100 100 100 100 100 100 100 100 100 100	1200

---

알고리즘 분류

● 다이나믹 프로그래밍
● 브루트포스 알고리즘
● 배낭문제

---

소스코드

package Lv2_Silver;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
/**
 * @author HanHoon
 * @category 다이나믹 프로그래밍, 브루트포스 알고리즘, 배낭문제
 * https://www.acmicpc.net/problem/1535
 */
public class BOJ_S2_1535_안녕 {
	static int result = 0;
	public static void backtracking(int visitCnt, int cnt, int start, int life, int happy, int N, int[] L, int[] J) {
		// 방문한 사람 == visitCnt 일때
		if(cnt == visitCnt) {
			// 살아있다면
			if(life > 0)
				// 행복 최대값 최신화
				result = Math.max(result, happy);
			return;
		}
		for (int i = start; i < N; i++) {
			life -= L[i];
			happy += J[i];
			backtracking(visitCnt, cnt+1, i+1, life, happy, N, L, J);
			life += L[i];
			happy -= J[i];
		}
	}
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = null;
		// 사람의 수
		int N = Integer.parseInt(br.readLine());
		// 잃는 체력
		int[] L = new int[N];
		st = new StringTokenizer(br.readLine(), " ");
		for (int i = 0; i < N; i++)
			L[i] = Integer.parseInt(st.nextToken());
		// 얻는 기쁨
		int[] J = new int[N];
		st = new StringTokenizer(br.readLine(), " ");
		for (int i = 0; i < N; i++)
			J[i] = Integer.parseInt(st.nextToken());

		for (int i = 1; i <= N; i++)
			backtracking(i, 0, 0, 100, 0, N, L, J);
		
		System.out.println(result);
		br.close();
	}
}

 

---

BaekJoon List

BaekJoon List

---

  

기회는 준비된 자에게 찾아온다.