[백준 - Java] 11057번 : 오르막 수

문제

www.acmicpc.net/problem/11057

11057번: 오르막 수

설명

DP 동적 계획법을 사용해 해결하는 문제이다.

표를 그려보면 dp를 적용할 규칙이 쉽게 떠오른다.

 

 

먼저 각 자릿수에는 0~9까지의 10개의 숫자가 들어갈 수 있다.

 

N=1 한자릿수일 경우 0~9까지 각 숫자들을 한 번씩 이용해 총 10가지의 오르막수를 만들 수 있다.

 

N=2 두자릿수일 경우

00, 01, 02 ... 09 -> 10 가지

11, 12, 13 ... 19 -> 9가지

22, 23 ... 29 -> 8가지

...

88, 89 -> 2가지

99 -> 1가지

로 총 55가지의 오르막수를 만들 수 있다.

 

즉, 0~9까지의 각 숫자(j)에서 만들 수 있는 오르막수는 이전 자릿수 N-1에서의 j부터 마지막 9까지의 합이다.

 

이를 코드로 표현해보겠다.

전체 코드

자릿수가 1인 경우, 각 숫자에서의 dp값이 모두 1 -> 이를 초기값으로 지정해줌

 

10007을 나누는 경우 나는 맨 마지막에 정답을 출력할 때만 나누어주면 된다고 생각했다.

하지만 dp계산 후에도 나머지연산을 해줘야 한다.

왜냐하면 자릿수가 40만 넘어가도 값이 한참 클터이니 dp후에도 모듈러 연산을 해준다.

 

* 모듈러 연산?

나눗셈

정수 두 개를 나누었을 때, 몫과 나머지를 구할 수 있다.

A / B = Q remainder R

 

이때 A는 피제수(dividend)라고 부른다.

B는 제수(divisor)라고 부른다.

Q는 몫(quotient)라고 부른다.

R는 나머지(remainder)라고 부른다.

모듈러(Modulo) 연산

나머지 연산은 modulo라고 하며 mod라고 나타낸다.

7 mod 2=17 mod 2=1 이다.

왜냐면 7을 2로 나누면 몫이 3이고 나머지가 1이므로, 이 나머지 값이 모듈러 연산의 결괏값이 된다.

 

그렇다면 −5 mod 3−5 mod 3 과 같은 경우는 어떻게 될까?

이러한 경우는 모듈러 연산의 특징을 이용해서 값을 구할 수 있다.

모듈러 연산은 피연산자의 값을 주기로 같은 결괏값을 갖는 주기성을 띤다. 따라서 다음과 같은 관계가 성립한다.

 

−5 mod 3=−2 mod 3=1 mod 3=4 mod 3...−5 mod 3=−2 mod 3=1 mod 3=4 mod 3...

 

즉 첫 번째 피연산자에 두 번째 피연산자의 정수배의 값을 더해도 같은 값이 나오는 것을 이용하여 문제를 해결할 수 있다.

다시 말해 -5에 3이나 6이나 9 등의 3∗K3∗K의 값을 더해도(단 KK는 정수) 결괏값은 같다는 것이다.

출처: https://eine.tistory.com/entry/수학-나머지 Modulo-연산-1 [아인 스트라세의 SW 블로그]

 

import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int[][] dp = new int[N+1][10];
		
		for(int i = 0; i < 10; i++) {
			dp[0][i] = 1;
		}
		
	
		for(int i = 1; i < N+1; i++) {
			for(int j = 0; j < 10; j++) {
				for(int k = j; k < 10; k++) {
					dp[i][j] += dp[i-1][k];
					dp[i][j] %= 10007;
				}
			}
		}
		
		System.out.println(dp[N][0] % 10007); 
	}

}

GITHUB

github.com/KwonMinha/BOJ/blob/master/BOJ%2311057/src/Main.java

KwonMinha/BOJ