문제

입력

출력

예제

idea

와 진짜 이놈의 dp 정신 나가겠다.
처음에는 재귀함수로 풀었는데 시간초과 나옴ㅜㅜㅜ
그래서 dp로 풀려는데 이게 머리로는 이해가 가는데 식으로 하려니 잘 안짜지더라..

정리

f[N][M] =f[N-1][N-1] + ... + f[N-1][M-1]

요걸 for문으로 짜려니깐 3중 for문이 되어버렸다..
디피를 재귀함수로 구현하려했는데 실패해서 그냥 바로 계산하도록 하였다.

요건 내 실패한 재귀함수식(결과는 잘 나옴)

import java.util.*;
import java.io.*;
public class Main {
	static int answer = 0;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		StringBuilder sb = new StringBuilder();
		int k=0;
		int x = Integer.parseInt(st.nextToken());
		for (int i = 0; i < x; i++) {
			answer =0;
			st = new StringTokenizer(br.readLine());
			int N = Integer.parseInt(st.nextToken());
			int M = Integer.parseInt(st.nextToken());			
			sb.append(bridge(N, M)).append("\n");		
		}
		System.out.println(sb);
	}
	public static int bridge(int N, int M) {
		for (int i = 1; i <= M - N + 1; i++) {
			if (N == 0) {
				answer++;
				break;
			}
			else	
				bridge(N - 1, M - i);
		}
		return answer;
	}
}

Code

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

public class Main {
	static int answer = 0;

	public static void main(String[] args) throws IOException {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		StringBuilder sb = new StringBuilder();
		int x = Integer.parseInt(st.nextToken());
		for (int i = 0; i < x; i++) {
			answer = 0;
			st = new StringTokenizer(br.readLine());
			int N = Integer.parseInt(st.nextToken());
			int M = Integer.parseInt(st.nextToken());
			int bridge[][] = new int[N + 1][M + 1];
			for (int j = 0; j <= M; j++) {
				bridge[0][j]=1;
				
			}
			for (int j = 1; j <= N; j++) {
				for (int k = j; k <= M; k++) {
					for(int t=j-1;t<k;t++)
						bridge[j][k] += bridge[j-1][t];
				}
			}

			sb.append(bridge[N][M]).append("\n");
		}
		System.out.println(sb);
	}

}

결과