풀이 방법
dp를 이용해서 모든 자리 수의 개수를 구해주었다.
자릿수는 마지막 자릿수가 0,1,2....9 일 경우 따로 갯수를 구하고 더해서 총합을 구하는 방식을 사용했다.
마지막 자리가 0으로 나오는 경우는 0~9까지 모두 나오고 1로 나오는 경우는 1~9, 2로 나오는 경우는 3~9까지 나온다.
예를 들면 4자리수 중 마지막 자릿수가 0으로 나오는 수는 3자리 수의 모든 경우에서 나오고 1로 나오는 수는 3자리 수에서 마지막 자릿수가 1~9인 경우만 나오게 된다.
내 코드
package com.company;
import java.io.*;
import java.util.*;
public class Main {
static int T;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
T = Integer.parseInt(br.readLine());
long[][] dp = new long[66][10];
for (int i = 0; i < 10; i++) {
dp[1][i] = 1;
}
for (int i = 2; i <= 65; i++) {
for (int j = 0; j < 10; j++) {
for (int k = j; k < 10; k++) {
dp[i][j] += dp[i - 1][k];
}
}
}
for (int i = 0; i < T; i++) {
int N = Integer.parseInt(br.readLine());
long answer = 0;
for (long j : dp[N]) {
answer += j;
}
System.out.println(answer);
}
}
}
'코딩테스트 > [백준] 코딩테스트 연습' 카테고리의 다른 글
숫자고르기 - 2668번 (0) | 2021.11.11 |
---|---|
문자열 잘라내기 - 2866번 (0) | 2021.11.09 |
팀 배정 - 18768번 (0) | 2021.11.08 |
거짓말 - 1043번 (0) | 2021.11.08 |
십자가 2개 놓기 - 17085번 (0) | 2021.11.05 |