[백준] 단계별로 풀어보기(단계:15,동적계획법1,JAVA)10844번, 쉬운 계단 수

문제 링크

10844번: 쉬운 계단 수

 

www.acmicpc.net

---

주의사항

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

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

---

문제 설명

---

접근 방법

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

 

계단수에 대한 정의는 문제에서 모두 알려주고 있습니다.

숫자의 길이가 길어지더라도 동일한 규칙이 존재합니다.

앞에 숫자가 0일 경우 : 뒤에 숫자는 1밖에 올 수 없다.

뒤에 숫자가 9일 경우 : 뒤에 숫자는 8밖에 올 수 없다.

그 이외에 숫자일 경우 : 뒤에 숫자는 이전 숫자＋1과 이전 숫자 - 1 만 올 수 있습니다.

예를 들어

길이가 4이고 789?의 상태이면 ?에는 숫자 8밖에 들어갈 수 있습니다.

길이가 4이고 210?의 상태이면 ?에는 숫자 1밖에 들어갈 수 있습니다.

길이가 4이고 234?의 상태이면 이전 숫자+1인 5와 이전 숫자-1인 3이 들어갈 수 있습니다.

 

길이마다 시작하는 숫자(0~9)에 따른 계단수를 저장하기 위해  [길이+1][10]으로 메모이제이션을 구성하였습니다.

 

 

• 함수 값 저장할 메모이제이션 배열 check를 만들었습니다.
• BufferedReader를 사용하여 입력 값을 받았습니다.
• 계단수의 개수를 얻는 함수 stair을 만들었습니다.
• for문을 통하여 시작하는 숫자에 맞게 함수를 실행하였으며 0으로 시작할 수 없으므로 범위를 1부터 시작하도록 설정하였습니다.
• System.out.println을 사용하여 결과를 출력하였습니다.

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

결과 코드

import java.io.*;
public class Main{
	static long[][] check;		//메모이제이션 배열
	static int num;		//입력값
	public static void main(String[] args) throws IOException{
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //BufferedReader를 통해 입력 값 받기
        //-------입력값 저장 및 배열 초기화----------------
    	num = Integer.parseInt(br.readLine());
    	check = new long[num+1][10];
    	long result=0;		//결과값
    	for(int i=1;i<=9;i++)
    		result +=stair(num, i);	//함수 호출
    	System.out.println(result%1000000000);	//결과 출력
    	br.close();
	}
    //------------계단수 구하는 함수---------------
	public static long stair(int depth, int start) {
		if(depth==1)		//길이만큼 완성했을 때
			return 1;
		//재귀
		if(check[depth][start]==0) {
			if(start==0)	//이전 숫자가 0일 때
				check[depth][start] = stair(depth-1,start+1);
			else if(start==9)	//이전 숫자가 9일 때
				check[depth][start] = stair(depth-1,start-1);
			else	//그 이외
				check[depth][start] = stair(depth-1,start+1) + stair(depth-1, start-1);
		}

		return check[depth][start]%1000000000;	//결과 반환
		}
	}