[코딩테스트] 백준(BAEKJOON) - 쉬운 계단 수(Java, 10844번)

 

안녕하세요~

 

오랜만에 인사드립니다.

다들 설날은 잘보내셨을까요~?

오랜만에 보는 친척들은 정말 반갑습니다~

 

사실 회사일에~ 스프링 공부에... 이 핑계 저 핑계대면서 코딩테스트에 소홀했습니다.

 

이러다가 다시 마음잡고 풀어볼까합니다.

오늘풀어볼 문제는 규칙만안다면 간단한!!(사실 DP문제들이 정작 코드는 짧긴하죠.. 이 규칙찾는게 너무어려운게 함정입니다.) 문제입니다.

 

문제 바로 만나보시죠~

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

10844번: 쉬운 계단 수

우리는 문제에서 제시하는 인접한 수, 즉 계단수를 찾아주면 되겠습니다.

앞의 수와 1차이나는 수들이 집합 즉 갯수의 합을 구해주면 되겠습니다.

 

그럼 저의 코드 먼저 만나보실까요?

import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Scanner;


public class Main {
		public static void main(String[] args) throws NumberFormatException, IOException {
			
			Scanner sc=new Scanner(System.in);
			int count=sc.nextInt();
			
			long[][] dp=new long[count+1][10];
			
			for(int i=1;i<=9;i++)
				dp[1][i]=1;
			
			if(count>1)
			{
				for(int i=2;i<=count;i++)
				{
					for(int j=0;j<=9;j++)
					{
						if(j==0)
							dp[i][0]=dp[i-1][1]%1000000000;
						else if(j==9)
							dp[i][9]=dp[i-1][8]%1000000000;
						else
						{
							dp[i][j]=(dp[i-1][j-1]+dp[i-1][j+1])%1000000000;
						}
					}
				}
			}
			
			long sum=0;
			for(int i=0;i<=9;i++)
				sum+=dp[count][i];
			
			System.out.println(sum%1000000000);	
	
	}

}

네 해당 이미지는제가 풀면서 생각했던걸 다시 정리할 내용입니다.

정리를 했으나 여전히 이해할 수 없네요. 이해를 잘했으면 잘 정리할 수 있다는데... 쉽지 않네요~

 

결론은 총 3가지의 케이스로 나뉩니다.

1) n번째의 j번째 숫자가 0일때는 n-1번째의 1번째의 값을 가져오고

2) n번째의 j번째 숫자가 9일때는 n-1번째의 8번째의 값을 가져오며

3) 나머지의 경우에는 n번째의 j번째는 n-1번째의 j-1번째 값과 j+1번째의 값의 합입니다.

 

위의 내용에서 제가 작성한것과 같이 끝자리가 5가 나오려면 앞자리가 -1인 4or +1인 6이여야만 가능합니다.

 

해당 내용이 도움이 되셨다면 좋겠네요~

 

오랜만에 쓰니 글에대한 감이 없네요 ㅠㅠ

오늘은 여기서 간단하게 마무리하겠습니다.

 

감사합니다. :D