백준 13302 - 리조트

Java

13302 번 - 리조트

문제

접근 방법

Bottom-up DP를 통해 해결하였다.

문제를 푼 후, 다른 분들의 풀이를 보니 조금 다른 점이 있었다.

내가 사용한 dp[a][b]는

a일째에 b개의 쿠폰을 가졌을 때까지 사용한 총 금액의 최소값

따라서, N 일째가 넘었을 때 사용한 총 금액을 구하고, 그 최소 금액이 정답이 된다.

코드

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

public class Main {
	static final int MAX_INT = 987654321, ONE_D = 10000, THREE_D = 25000, FIVE_D = 37000;
	static int n, m, result = MAX_INT;
	static int[][] dp;
	static boolean[] plan;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	StringTokenizer stk = new StringTokenizer(br.readLine());
    	n = stoi(stk.nextToken());
    	m = stoi(stk.nextToken());

    	plan = new boolean[n + 1];
    	dp = new int[n + 1][100];

    	for(int i = 0; i <= n; i++) {
    		Arrays.fill(dp[i], MAX_INT);
    	}

    	Arrays.fill(plan, true);

    	// m이 0이면 다음 입력을 받지 않는다.
    	if(m != 0)
    		stk = new StringTokenizer(br.readLine());
    	int curD;
    	for(int i = 0; i < m; i++) {
    		curD = stoi(stk.nextToken());
    		plan[curD] = false;
    	}

    	DFS(1,0,0);
    	System.out.println(result);
    	br.close();
	}

	static void DFS(int day, int cupon, int sum) {
		// 총 금액의 최소를 구한다.
		if(day > n) {
			result = Math.min(sum, result);
			return;
		}
		// day 번째 날 cupon 개의 쿠폰을 가지고 있을 때까지 사용한 최소 금액을 구한다.
		if(dp[day][cupon] > sum) {
			dp[day][cupon] = sum;
		}
		else {
			return;
		}
		//휴일 일 때
		if(!plan[day]) {
			DFS(day + 1, cupon, sum);
		}
		// 쿠폰이 3장 이상일 때
		if(cupon >= 3) {
			DFS(day + 1, cupon - 3, sum);
		}

		DFS(day + 1, cupon, sum + ONE_D);
		DFS(day + 3, cupon + 1, sum + THREE_D);
		DFS(day + 5, cupon + 2, sum + FIVE_D);
	}

	static int stoi(String str) {
    	return Integer.parseInt(str);
    }
}

Top - down 방식으로 해결하면

dp[a][b]를 a번째 날, b개의 쿠폰을 가지고 있을 때, 리조트에 들어가는데 들어가는 최소비용 이라고 생각하여 다음과 같이 풀수있다.

static int DFS(int day, int cupon) {
  if(day > n) {
    return 0;
  }
  // 이미 한번 방문했으면 추가로 방문하지 않는다.
  if(dp[day][cupon] != MAX_INT) {
    return dp[day][cupon];
  }

  // 만약 방문하지 않는 날일 때
  if(!plan[day]) {
    return dp[day][cupon] = DFS(day + 1, cupon);
  }

  dp[day][cupon] = Math.min(dp[day][cupon], DFS(day + 1, cupon) + ONE_D);
  dp[day][cupon] = Math.min(dp[day][cupon], DFS(day + 3, cupon + 1) + THREE_D);
  dp[day][cupon] = Math.min(dp[day][cupon], DFS(day + 5, cupon + 2) + FIVE_D);

  if(cupon >= 3) {
    dp[day][cupon] = Math.min(dp[day][cupon], DFS(day + 1, cupon - 3));
  }
  return dp[day][cupon];
}

위 두 코드의 차이는, dp[a][b]에서 a 일자가 흘러가며 돈을 쌓아가는 방식인가(Bottom-Up), 아님 dp[1][0]으로 모이는 것인가(Top-down)의 차이이다.

총평

후기

해당 블로그가 많이 도움되었다.

https://yabmoons.tistory.com/405

개선할 점