[BOJ2688/Java] 줄어들지 않아

문제 요약

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

2688번: 줄어들지 않아

우리는 문제에서 N자리 어떤 숫자의 각 자리수보다 그 왼쪽 수가 작거나 같은 줄어들지 않는 수가 몇 개 있는지 알아보고 싶다. 문제 조건은 간단하지만 이를 어떤식으로 구현할지는 고민이 필요했던 문제라고  생각했다.

입/출력

 

접근 아이디어

1. 이전에 생성된 줄어들지 않는 수를 이용하는 dp

이 방법은 처음에 생각한 방식인데 세자리 줄어들지 않는 수를 만드려면 일단 두자리 줄어들지 않는 수가 필요하다. 즉 이전에 만들어진 줄어들지 않는 수(ex. 01)에 새로운 수(ex. 이경우는 1이상)를 붙이면 자리수가 늘어난 새로운 줄어들지 않는 수가 생긴다. 즉 이전 단계에서의 줄어들지 않는 수의 개수를 이용한다면 그 다음 단계의 줄어들지 않는 수의 개수를 알 수 있다. 이를 코드로 구현하기 위해서 2차원 dp 배열을 선언하고 배열의 값은

r행 c열이라고 하면 r 자리수에 c 이하의 수로 끝나는 줄어들지 않는 수를 저장하고 있다.

즉 모든 줄어들지 않는 세자리수를 구하기 위해서는 dp[3][9]에 접근하면 된다.

 

그리고 dp 내부 값은 0행과 0열은 모두 1로 초기화하고 시작한다.

r자리 수에서 c 이하의 수로 끝나는 수를 구하기 위해서는

r-1자리 수에서 c이하의 수로 끝나는 수의 개수 + r자리 수에서 c-1 이하의 수로 끝나는 수의 개수를

구해서 집어 넣으면 된다.

끝!

 

 

2. 중복조합을 활용한 dp

이건 사실 복습하려고 문제 다시 열었다가 생각난건데

n자리수 줄어들지 않는 모든 수의 개수를 찾는 것은 중복조합과 같다.

중복조합을 구현하자

 

시간 복잡도

=> 시간 복잡도는 N이나 이차원배열이기 때문에 어느정도 복잡도가 있긴함

 

구현 코드 1(dp)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {

	static int N;
	static long[][] dp;
	
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		int T = Integer.parseInt(br.readLine());
		
		for(int tc = 0; tc<T; tc++) {
			N = Integer.parseInt(br.readLine());
			dp= new long[N+1][10];
			
			for(int i = 1; i<10; i++) {
				dp[0][i] = 1;
			}
			int sum = 0;
			for(int i = 1; i<=N; i++) {
				dp[i][0] = 1;
				for(int j = 1; j<10; j++) {
					dp[i][j] = dp[i][j-1]+dp[i-1][j];
				}
			}
			
			sb.append(dp[N][9]).append('\n');
		}
		System.out.println(sb);
	}

}

 

구현코드2(중복조합)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {

	static int N;
	static long[][] dp;
	
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		int T = Integer.parseInt(br.readLine());
		
		for(int tc = 0; tc<T; tc++) {
			N = Integer.parseInt(br.readLine());
			sb.append(combi(10+N-1, N)).append('\n');
		}
		System.out.println(sb);
	}
	
	static long combi(int n, int r) {
		dp = new long[n+1][r+1];
		for(int i = 0; i<=n; i++) {
			for(int j = 0; j<=i && j<=r;j++) {
				if(j == 0 || j == i) {
					dp[i][j] = 1;
					continue;
				}
				dp[i][j] = dp[i-1][j-1]+dp[i-1][j];
			}
		}
		return dp[n][r];
	}
}