[백준] 단계별로 풀어보기(단계:15,동적계획법1,JAVA)2579번, 계단 오르기

문제 링크

2579번: 계단 오르기

 

www.acmicpc.net

---

주의사항

• JAVA를 사용하여 프로그램을 사용하였습니다.
• 백준에서 코드를 작성하였을 때 아래 형태에서 Main에서 결과가 출력되어야 합니다.

public class Main{ 	
	public static void main(String[] args){
    }
}

---

문제 설명

---

접근 방법

동적계획법이란 위 문제와 같이 동일한 연산을 계속 반복하여 비효율적으로 코드가 실행되어 그것을 향상시키기 위하여반복되는 연산의 결과를 따로 저장하여 적재적소에 코드가 더 효율적으로 만드는 방법입니다.

 

예제 1에 최대값일 때를 표현하면

10 ▶ 20 ▶ 25 ▶ 20 = 70

 

규칙은 문제에서 모두 알려주고 있습니다.

시작위치는 아무것도 없는 것으로 0으로 초기화 한 뒤 1칸으로 이동했을 때와 2칸으로 이동했을 때에 경우의 수를 구하여 최대값을 구하도록 하였습니다.

계단 위치와 몇 번 연속되었는지에 따라 달라지므로 [계단크기+1][3]으로 메모이제이션을 구성하였습니다.

stack은 연속되었을 때를 나타냅니다.그래서 stack=2일 때는 두 칸으로 넘어가야 합니다.계단의 크기-1에 계단에서 2칸으로 이동하면 계단을 넘어가는 것이기 때문에 -10000을 넣어 최대값이 될 수 없게 하였습니다.

 

• 함수 값 저장할 메모이제이션 배열 check를 만들었습니다.
• 계단에 상응하는 값을 저장하는 stair을 만들었습니다.
• BufferedReader를 사용하여 입력 값을 받았습니다.
• 계단을 올라갈 때 최대값을 얻는 함수 stairCal을 만들었습니다.

• check가 null이 아니면 메모이제이션에 저장된 값이 있기에 그 값을 가져온다.
• null인 경우 재귀를 반복하여 결과값을 메모이제이션에 저장한 뒤 반환한다.
• 위에 알고리즘 설명을 토대로 재귀하도록 stairCal함수를 작성하였습니다.

결과 코드

import java.io.*;
public class Main{
	static Integer[][] check;	//메모이제이션 배열
	static Integer[] stair;		//계단 배열
	static int index;
	public static void main(String[] args) throws IOException{
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //BufferedReader를 통해 입력 값 받기
        //------------입력값 저장 및 배열 초기화------------
    	index = Integer.parseInt(br.readLine());
    	stair = new Integer[index+1];
    	check = new Integer[index+1][3];
    	stair[0] = 0;		//시작 위치는 숫자가 없음
    	for(int i=1;i<=index;i++) 
    		stair[i] = Integer.parseInt(br.readLine());
    	
    	System.out.println(stairCal(0, 0) + "\n");	//결과 출력
    	br.close();
	}
    //------------계단 오르기 최대값 구하는 함수--------------
	public static Integer stairCal(int depth, int stack) {
		if(depth>index)
			return -10000;	//도착점 넘어갈때
		
		if(depth==index)	//도착점에 왔을 때
			return stair[depth];
	
		if(check[depth][stack]!=null)	//메모이제이션에 값 존재시
			return check[depth][stack];
		
		if(stack==2)	//연속 2번 1칸으로 계단올랐을 때
			check[depth][stack] = stairCal(depth+2, 1) + stair[depth];
		else	//재귀
			check[depth][stack] = Math.max(stairCal(depth+1, stack+1), 
            stairCal(depth+2, 1)) + stair[depth];

		return check[depth][stack];	//결과 반환
		}
	}