반응형
문제출처
https://www.acmicpc.net/problem/14501
dp문제이나 n이 충분히 작기때문에 dfs로도 풀 수 있는 문제이다. 삼성기출문제인데 dp개념이 확실하지 않아 점화식을 세우는데 어려움이 있었다 .
풀이 과정
/**
* day 1 2 3 4 5 6 7
* =====================================
* t 3 5 1 1 2 4 2
* p 10 20 10 20 15 40 200
*
* i에서 시작해서 퇴사일 까지 최대 값을 dp[i]에 저장합니다.
* dp[i]는 두가지 중 최대값을 저장하면 된다. (i == 일)
* 1) 오늘의 스케쥴을 하는 경우 : dp[i + t[i]] + p[i]
* 2) 오늘의 스케쥴을 안 하는 경우 : dp[i+1]
/*
* 즉 solve(0) = Math.max(solve(1), solve(0 + t[0]) + p[0])
* .
* .
* .
* .
* .
* solve(6) = Math.max(solve(7), solve(8)+200
*
* 과 같이 나열된다. 하지만 여기서 7일까지만 일하므로 8일차는 범위를 벗어난 경우이다.
* 때문에 -값을 주어 max에 영향을 주지 않도록 조치한다.
* 이 재귀를 풀어서 역으로 추적하면 쉽게 답을 구할 수 있다.
*/
소스코드
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 | import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.Arrays; import java.util.StringTokenizer; public class Main { public static final int INF = 0x7fffffff; public static final int MAX =16; public static int[] t = new int[MAX]; public static int[] p = new int[MAX]; public static int[] dp = new int[MAX]; public static int n; public static void main(String[] args) throws Exception { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); n = Integer.parseInt(br.readLine()); // input data... for (int i = 0; i <n; i++) { StringTokenizer st = new StringTokenizer(br.readLine()); t[i] = Integer.parseInt(st.nextToken()); p[i] = Integer.parseInt(st.nextToken()); } Arrays.fill(dp, -1); int ret=solve(0); System.out.println(ret); } public static int solve(int s) { if(s==n) return 0; if(s>n) return -INF; int ret=dp[s]; if(ret!=-1) return ret; ret=Math.max(solve(s+1), solve(s+t[s]) + p[s]); return ret; } } | cs |
아래와 같은 풀이도 존재한다.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 | #include <cstdio> using namespace std; int dp[25]; int max(int a, int b) { return a > b ? a : b; } int main() { int N; int t, p; scanf("%d", &N); for (int i = 0; i < N; i++) { scanf("%d %d", &t, &p); dp[i + 1] = max(dp[i + 1], dp[i]); dp[i + t] = max(dp[i + t], dp[i] + p); } printf("%d\n", dp[N]); } | cs |
반응형
'Algorithm' 카테고리의 다른 글
| [SWEA 1245] 균형점 (0) | 2019.01.15 |
|---|---|
| [BOJ 1463] 1로 만들기 (0) | 2019.01.14 |
| [BOJ 1182] 부분집합의 합 (0) | 2019.01.14 |
| [BOJ 1543] 문서 검색 (0) | 2019.01.08 |
| [BOJ 2941] 크로아티아 알파벳 (0) | 2019.01.07 |
