[백준] JAVA - 1535.안녕

 

1월 5주차 알고리즘 스터디에서 진행한 DP 문제이다. 문제에서 구하려는것은 주어진 체력안에서 얻을수있는 최대 기쁨값이다.

 

DP로 풀수있는 문제들은 처음 주어진 문제들을 더 작은 문제들로 나눌 수 있다는것이 특징이다. 즉 이렇게 작게 나누어진 부분문제들로 이들의 답을 통해 원래 문제에 대한 답을 구할수있는것이 핵심이다. DP 에서는 부분문제들이 여러번 재사용될수있기 때문에 이들의 값을 따로 저장하는 기법(Cache, Memoization)을 잘 사용하면 효율적으로 풀수있다.

 

보통 DP 문제들을 보면 점화식을 세우고 이를 재귀적으로 풀이하는 코드가 많지만 나는 이 문제를 보고 재귀적으로 구현하는게 부족해서 손으로 직접 써가면서 문제를 풀었다. 마음은 재귀로 풀고싶었지만 그렇게 풀지 못해서 다른 스터디원이 재귀로 푼 코드를 보고 감탄했다..

 

이 문제에서는 인사를 할수도있고 안할수도있는 두가지 경우가 있다. 또 각각의 경우에서 또 다시 두가지 경우가 나뉘기 때문에 이를 DP 방식으로 풀수있었다.

 

 

내가 세운 점화식은 아래와 같다.

dp[i][j] : i번째까지 거쳐왔을때 남은 체력이 j 일때의 최대 기쁨 값

• 처음 가지고 있는 체력에서 인사를 할수있는경우와 인사를 못하는 경우로 나눈다.
• i번한테 인사를 할수있는경우 인사를 하는경우와 안하는경우 중 최대값을 저장한다.
• 체력이 100까지이므로 체력이 1이 되었을때가 가장 큰 기쁨값을 가지고 있다 -> dp[N][99]

JAVA 코드

import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		
		int[] hp = new int[21];
		int[] joy = new int[21];
		
		int[][] dp = new int[21][101];
		
		//입력부분
		for (int j = 1; j <= N; j++) {
			hp[j] = sc.nextInt();
			
		}
		for (int j = 1; j <= N; j++) {
			joy[j] = sc.nextInt();
		}
		
		for (int i = 1; i <= N; i++) {
			for (int j = 1; j <= 99; j++) {
				//i번한테 인사를 할수있는 경우
				if(hp[i] <= j)
					//i한테 인사안하는경우, 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];
			}
		}
		
		System.out.println(dp[N][99]);

	}
	


}

 

스터디원의 재귀 풀이

import java.util.Scanner;

public class Main {
    private static final Scanner SCANNER = new Scanner(System.in);
    private static int n;   /// 사람의 수
    private static int[] healthMinus; // 체력 잃는 수
    private static int[] pleasurePlus; // 기쁨 얻는 수

    public static void main(String[] args) {
        n = SCANNER.nextInt();
        healthMinus = new int[n];
        pleasurePlus = new int[n];

        for (int i = 0; i < n; i++) {
            healthMinus[i] = SCANNER.nextInt();
        }
        for (int i = 0; i < n; i++) {
            pleasurePlus[i] = SCANNER.nextInt();
        }
        System.out.println(go(0, 0, 0));
    }

    public static int go(int index, int now_life, int sum){
        if(now_life >= 100) {
            return 0;
        }
        if(index == n) {
            return sum;
        }
        int answer = 0;

        answer = Math.max(answer, go(index+1,
                now_life+healthMinus[index], sum+pleasurePlus[index]));

        answer = Math.max(answer, go(index+1,
                now_life, sum));

        return answer;
    }
}

※ 공유를 허락해주신 스터디원분 깃헙주소입니다!! github.com/kwj1270