๐ ๋ฌธ์
https://www.acmicpc.net/problem/14501
๋ฌธ์
์๋ด์์ผ๋ก ์ผํ๊ณ ์๋ ๋ฐฑ์ค์ด๋ ํด์ฌ๋ฅผ ํ๋ ค๊ณ ํ๋ค.
์ค๋๋ถํฐ N+1์ผ์งธ ๋๋ ๋ ํด์ฌ๋ฅผ ํ๊ธฐ ์ํด์, ๋จ์ N์ผ ๋์ ์ต๋ํ ๋ง์ ์๋ด์ ํ๋ ค๊ณ ํ๋ค.
๋ฐฑ์ค์ด๋ ๋น์์๊ฒ ์ต๋ํ ๋ง์ ์๋ด์ ์ก์ผ๋ผ๊ณ ๋ถํ์ ํ๊ณ , ๋น์๋ ํ๋ฃจ์ ํ๋์ฉ ์๋ก ๋ค๋ฅธ ์ฌ๋์ ์๋ด์ ์ก์๋์๋ค.
๊ฐ๊ฐ์ ์๋ด์ ์๋ด์ ์๋ฃํ๋๋ฐ ๊ฑธ๋ฆฌ๋ ๊ธฐ๊ฐ Ti์ ์๋ด์ ํ์ ๋ ๋ฐ์ ์ ์๋ ๊ธ์ก Pi๋ก ์ด๋ฃจ์ด์ ธ ์๋ค.
N = 7์ธ ๊ฒฝ์ฐ์ ๋ค์๊ณผ ๊ฐ์ ์๋ด ์ผ์ ํ๋ฅผ ๋ณด์.
1์ผ 2์ผ 3์ผ 4์ผ 5์ผ 6์ผ 7์ผ
ti | 3 | 5 | 1 | 1 | 2 | 4 | 2 |
pi | 10 | 20 | 10 | 20 | 15 | 40 | 200 |
1์ผ์ ์กํ์๋ ์๋ด์ ์ด 3์ผ์ด ๊ฑธ๋ฆฌ๋ฉฐ, ์๋ดํ์ ๋ ๋ฐ์ ์ ์๋ ๊ธ์ก์ 10์ด๋ค. 5์ผ์ ์กํ์๋ ์๋ด์ ์ด 2์ผ์ด ๊ฑธ๋ฆฌ๋ฉฐ, ๋ฐ์ ์ ์๋ ๊ธ์ก์ 15์ด๋ค.
์๋ด์ ํ๋๋ฐ ํ์ํ ๊ธฐ๊ฐ์ 1์ผ๋ณด๋ค ํด ์ ์๊ธฐ ๋๋ฌธ์, ๋ชจ๋ ์๋ด์ ํ ์๋ ์๋ค. ์๋ฅผ ๋ค์ด์ 1์ผ์ ์๋ด์ ํ๊ฒ ๋๋ฉด, 2์ผ, 3์ผ์ ์๋ ์๋ด์ ํ ์ ์๊ฒ ๋๋ค. 2์ผ์ ์๋ ์๋ด์ ํ๊ฒ ๋๋ฉด, 3, 4, 5, 6์ผ์ ์กํ์๋ ์๋ด์ ํ ์ ์๋ค.
๋ํ, N+1์ผ์งธ์๋ ํ์ฌ์ ์๊ธฐ ๋๋ฌธ์, 6, 7์ผ์ ์๋ ์๋ด์ ํ ์ ์๋ค.
ํด์ฌ ์ ์ ํ ์ ์๋ ์๋ด์ ์ต๋ ์ด์ต์ 1์ผ, 4์ผ, 5์ผ์ ์๋ ์๋ด์ ํ๋ ๊ฒ์ด๋ฉฐ, ์ด๋์ ์ด์ต์ 10+20+15=45์ด๋ค.
์๋ด์ ์ ์ ํ ํ์ ๋, ๋ฐฑ์ค์ด๊ฐ ์ป์ ์ ์๋ ์ต๋ ์์ต์ ๊ตฌํ๋ ํ๋ก๊ทธ๋จ์ ์์ฑํ์์ค.
์ ๋ ฅ
์ฒซ์งธ ์ค์ N (1 ≤ N ≤ 15)์ด ์ฃผ์ด์ง๋ค.
๋์งธ ์ค๋ถํฐ N๊ฐ์ ์ค์ Ti์ Pi๊ฐ ๊ณต๋ฐฑ์ผ๋ก ๊ตฌ๋ถ๋์ด์ ์ฃผ์ด์ง๋ฉฐ, 1์ผ๋ถํฐ N์ผ๊น์ง ์์๋๋ก ์ฃผ์ด์ง๋ค. (1 ≤ Ti ≤ 5, 1 ≤ Pi ≤ 1,000)
์ถ๋ ฅ
์ฒซ์งธ ์ค์ ๋ฐฑ์ค์ด๊ฐ ์ป์ ์ ์๋ ์ต๋ ์ด์ต์ ์ถ๋ ฅํ๋ค.
โ๏ธ ํ์ด
์ผ๋ฐ์ ์ธ DFS ํ์ด์ ์ข ๋ ๋น ๋ฅธ DP ํ์ด, ๋ ๊ฐ์ง ๋ฐฉ๋ฒ์ด ์๋ค.
๊ฐ์ธ์ ์ผ๋ก DFS๊ฐ ๋ ์ง๊ด์ ์ด๊ณ ์๋ฟ์ง๋ง.....๋๋๊ฐ ์ค๋ฒ3์ด๋ ๊ทธ๋๋ง ํต๊ณผ๋์ง, ์กฐ๊ธ๋ง ์ฌ๋ผ๊ฐ๋ฉด ์๊ฐ์ด๊ณผ๊ฐ ๋ ๊ฒ์ด ๋ปํ๊ธฐ์, ํ ์ ์์ด DP๋ก๋ ํ์๋ค. (ใ ใ ) ๋ DP๊ฐ ํญ์ ์ด๋ ต๋ค....
โ๏ธ DFS
โป๏ธ ์ฒซ๋ ๋ถํฐ ํ์ฌ ์ผ์ ์ ํํ๋ ๊ฒฝ์ฐ/ ์ํ๋ ๊ฒฝ์ฐ๋ฅผ ๋๋ ์ ๊น์ดํ์์ ํ๋ค.
โป๏ธ ํ์ฌ ์ผ์ ์ ํํ ๊ฒฝ์ฐ, ์ผ์ ์๋ฃํ๋๋ฐ ๊ฑธ๋ฆฌ๋ ์๊ฐ์ด ํด์ฌ์ผ์ ๋์ง ์์์ผ ํ๋ค. ๋์ง ์๋๋ค๋ฉด, ๋ฐ์ ๊ธ์ก์ ์ด์ต์ ๋ํ ํ ํ์ฌ ์ผ์ ๋ง์ณค์ ๋์ ์ผ์๋ก ๋์ด๊ฐ์ DFS ํ์์ ๋ฐ๋ณตํ๋ค.
ํ์ฌ ์ผ์ ์ ํํ์ง ์์ ๊ฒฝ์ฐ, ์ด์ต์ ๊ทธ๋๋ก ๋ ์ฑ ๋ค์๋ ๋ก ๋์ด๊ฐ DFS ํ์์ ๋ฐ๋ณตํ๋ค.
โป๏ธ ํด์ฌ์ผ์ ๋ค๋ค๋ฅด๋ฉด ํ์ฌ๊น์ง ๊ณ์ฐํ ์ด์ต์ ๋น๊ตํ์ฌ ํฐ ์ชฝ์ผ๋ก ์ ๋ฐ์ดํธํ๋ค.
โ๏ธ DP
๐ก ์ญ์์ผ๋ก ์ ๊ทผํ๋ค.
์ญ์์ผ๋ก ์ ๊ทผํ๋ ๊ฐ๋ ์ ํ๋์ฉ ์ฐจ๋ถํ ์๋ฎฌ๋ ์ด์ ์ ๋๋ ค๋ณด์ง ์์ผ๋ฉด ๋จ๋ฒ์ ์ดํดํ๊ธฐ๊ฐ ํ๋ค๋ค.
โป๏ธ ํ์ฌ ์ผ์ ์ ํํ ์ ์๋ ๊ฒฝ์ฐ, ํ์ฌ์ ์ด์ต์ ๋ค์๋ ์ ์ด์ต์ด ๋๋ค. (ํ์ฌ ์ผ์ ํ์ง ์์ผ๋ฉด ๋ค์๋ ์ผ์ ํ๊ฒ ๋๋ฏ๋ก)
โป๏ธ ํ์ฌ ์ผ์ ์ ํํ ์ ์๋ ๊ฒฝ์ฐ, (ํ์ฌ ์ผ์ ์ด์ต์ ์ผ์ ์๋ฃํ ๋ ์ ์ด์ต์ ๋ํ ๊ฐ-์ผ์ ์ด์ด์ ํ๊ฒ ๋๋ฏ๋ก)๊ณผ (์ด ์ผ์ ํ์ง ์๊ณ ๋ค์๋ ์ผ์ ํ์ ๊ฒฝ์ฐ์ ๊ฐ) ์ค ํฐ ๊ฐ์ด ํ์ฌ์ ์ด์ต์ด ๋๋ค.
๐ก ๋๋ N์ผ์ด ์์ ๊ฒฝ์ฐ 1~N์ผ๋ก ์์ํ๊ฒ ๋ง์ท๊ธฐ ๋๋ฌธ์, ํน์ ์ผ X๋ถํฐ D์ผ์ ์ผํ๊ฒ ๋๋ค๋ฉด X ๋น์ผ์ ํ๋ฃจ๋ก ์ณ์ค์ผ ํ๋ค. ๋ฐ๋ผ์ ๊ณ์ฐ์์ X-1+D๋ก ๊ณ์ฐ์ ํ๊ฒ ๋๋ค.
์๋ฅผ ๋ค์ด ์ด 7์ผ์ด ์์ ๊ฒฝ์ฐ, ๋ง์ง๋ง ๋ 7์ผ์ 1์ผ์ ์ผํ๋ค๋ฉด 7-1+1=7๋ก ํด์ฌ์ผ์ ๋๊ธฐ์ง ์๊ฒ ๋๋ ๊ฒ์ด๋ค.
๐ป ์์ค์ฝ๋: ์๋ฐ(Java)
public class Main_๋ฐฑ์ค_14501_ํด์ฌ_์ค๋ฒ3 {
static int N, result=0;
static int[][] day;
static int[] dp;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
N = Integer.parseInt(br.readLine());
day = new int[N+1][2];
dp = new int[N];
for (int i = 1; i <= N; i++) {
StringTokenizer st = new StringTokenizer(br.readLine());
day[i][0] = Integer.parseInt(st.nextToken());
day[i][1] = Integer.parseInt(st.nextToken());
}//input
dfs(1,0);
System.out.println(result);
}//end of main
private static void dfs(int idx, int profit) {
if(idx>N) {
result = Math.max(result, profit);
return;
}
int d = day[idx][0];
int p = day[idx][1];
if(idx+d-1<=N) dfs(idx+d, profit+p);
dfs(idx+1, profit);
}//end of dfs
private static void dp() {
for (int i = N; i >= 1; i--) { //๋ง์ง๋ง ๋ ๋ถํฐ ํ์ธ
int d = day[i][0];
int p = day[i][1];
if(i-1+d <= N) { // i+d<=N+1์ด์๋๋ฐ ๋ ์ดํดํ๊ธฐ ์ฝ๊ฒ ๊ณ ์ณค๋ค
dp[i] = Math.max(p+dp[i+d], dp[i+1]);
}else {
dp[i] = dp[i+1];
}
}
}//end of dp
}//end of class
๐ ๐ ๐
๏ผฐ๏ฝ๏ฝ๏ฝ๏ฝ ๏ฝ ๏ผข๏ฝ ๏ผณ๏ผก๏ผน
๐๐ฉ๐ข๐ฏ๐ฌ๐ด ๐ง๐ฐ๐ณ ๐ณ๐ฆ๐ข๐ฅ๐ช๐ฏ๐จ