백준 #2688 줄어들지 않아

어떤 숫자가 줄어들지 않는다는 것은 그 숫자의 각 자리 수보다 그 왼쪽 자리 수가 작거나 같을 때 이다.

예를 들어, 1234는 줄어들지 않는다.

줄어들지 않는 4자리 수를 예를 들어 보면 0011, 1111, 1112, 1122, 2223이 있다. 줄어들지 않는 4자리수는 총 715개가 있다.

이 문제에서는 숫자의 앞에 0(leading zero)이 있어도 된다. 0000, 0001, 0002는 올바른 줄어들지 않는 4자리수이다.

n이 주어졌을 때, 줄어들지 않는 n자리 수의 개수를 구하는 프로그램을 작성하시오.

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

 

---

 

DP문제입니다!

문제를 풀면서 알았는데 문제의 특징을 뽑아 점화식을 설계하면 편리한거 같습니다.

 

• 자릿수 n이 주어지고 줄어들지 않는 n자리 수의 개수를 구하면 된다.
• 숫자 n은 왼쪽 숫자보다 크거나 같아야한다.

두 특징을 이용해서 dp[자릿수][가장 오른쪽에 있는 숫자]으로 배열을 만들어주었습니다.

dp[i][j]에서 i = (자릿수), j = (가장 오른쪽에 있는 숫자)라고 했을 때 규칙을 생각해보면

 

• i = 0  일 때는 존재하지 않습니다.
• i = 1 일 때는 j = 1, j = 2, j = 3 … j = 9 한 개씩 존재합니다.

i = 2부터 생각해봅시다.

 

• dp[2][0]일 때는 00 한 가지
• dp[2][1]일 때는 01, 11 두 가지
• dp[2][2]일 때는 02, 12, 22 세 가지
• dp[2][3]일 때는 03, 13, 23, 33 네 가지
• 마찬가지로 dp[2][9]일 때는 09, 19, 29, 39, 49, 59, 69, 79, 89, 99 아홉 가지

i = 3일 때 경우의 수를 찾아보면

 

• dp[3][0] 일 때는 000 한 가지
• dp[3][1] 일 때는 001, 011, 111 세 가지
• dp[3][2] 일 때는 002, 012, 022, 222, 112, 122 여섯 가지

i = 3 일 때 규칙을 식으로 세워보면 dp[3][2] = dp[2][2] + dp[2][1] + dp[2][0]가 됩니다.

i = 2 역시 dp[2][2] = dp[1][2] + dp[1][1] + dp[1][0]가 됩니다.

 

이제 이 규칙을 코드로 만들면 됩니다.

typedef long long ll;
ll dp[65][11] = {}; // 경우의 수가 int 자료형을 넘어감
// ...
int n;
cin >> n;

for(int i = 2; i <= n; i++) {
	dp[i][0] = 1;
  ll k = 0;
  for(int j = 0; j <= 9; j++) {
	  dp[i][j] = dp[i - 1][j] + k;
    k += dp[i - 1][j];
  }
}

ll result = 0;
for(int i = 0; i <= 9; i++) {
	result += dp[n][i];
}

cout << result << "\n";
// ...

 

 

맞았습니다!!