BOJ::2579 계단 오르기

https://www.acmicpc.net/problem/2579


dp문제이다.

포도주 문제와 비슷한데 조건이 좀더 까다롭다.

그치만 점화식만 세울 수 있으면 풀 수 있다.

나는 두가지 방법으로 풀어 보았다.


<첫번째 방법>


N번째 경우에 대해

d[n]=a[n]+max(d[i-2],d[i-3]+a[i-1]) 이라는 점화식을 세웠다.

연속으로 3번을 오를 수 없기 때문에 n번째 올라 갈 수 있는 경우는 2가지 방법 뿐이다.


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
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
 
public class Main {
    
    static int a[]=new int[301];
    static int d[]=new int[301];
    
    public static void main(String args[]) throws NumberFormatException, IOException
    {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n=Integer.parseInt(br.readLine());
        for(int i = 1 ; i <= n ; i++){
            a[i]=Integer.parseInt(br.readLine());
        }
        
        d[1]=a[1];
        d[2]=a[2]+a[1];
        d[3]=a[3]+Math.max(a[1], a[2]);
        for(int i = 4 ; i <= n ; i++){
            d[i]=a[i]+Math.max(d[i-2], d[i-3]+a[i-1]);
        }
        
        System.out.println(d[n]);
    }
    
}
cs




<두번째 방법>


N번째 계단을 오를때 그 계단이 연속으로 1번째인지, 2번째인지를 나눠서 점화식을 세웠다.


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
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Main {
    
    public static void main(String args[]) throws IOException
    {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        int a [] = new int[n+1];
        int d[][] = new int [301][3];
        
        for(int i = 1 ; i <= n ; i ++)
        {
            a[i] = Integer.parseInt(br.readLine());
        }
        
        d[1][1] = a[1];
        d[1][2] = 0;
        d[2][1] = a[2];
        d[2][2] = d[1][1] + a[2];
        
        for(int i = 3; i <= n ; i++)
        {
            d[i][1] = Math.max(d[i-2][1], d[i-2][2]) + a[i];
            d[i][2] = d[i-1][1] + a[i];
        }
        
        //d[n][1]:n번째 계단을 1번 연속으로 밟은 경우
        //d[n][2]:n번째 계단을 2번 연속으로 밟은 경우
        System.out.println(Math.max(d[n][1], d[n][2]));
        
    }
}
cs


저작자표시

'BOJ::문제풀이' 카테고리의 다른 글

2667 단지 번호 붙이기  (0) 2018.01.05
2589 보물섬  (0) 2018.01.04
2573 빙산  (0) 2018.01.01
2563 색종이  (0) 2018.01.01
2309 일곱 난쟁이  (0) 2018.01.01

+ Recent posts

티스토리툴바