Algorithm
코드트리
두 배까지 커지는 수열

문제

https://www.codetree.ai/problems/a-sequence-greater-than-twice/description (opens in a new tab)

내 풀이

import java.util.*;
import java.io.*;
 
public class Main {
    public static Long dividor = 1000000007L;
    public static Long combCnt = 0L;
 
    public static int n;
    public static int m;
    public static int max;
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
 
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        max = getMax(n - 1);
 
        for(int i = 1; i <= max; i ++) {
            comb(1, i);
        }
 
        // 자바 나머지 연산 헷갈림
        // long to int 헷갈림
        int result = (int) (combCnt % dividor);
        System.out.println(result);
    }
 
    public static int getMax(int x) {
        int result = m;
        for(int i = 0; i < x; i++) {
            result /= 2;
        }
        return result;
    }
 
    public static void comb(int depth, int value) {
        if(depth == n) {
            combCnt ++;
        }
        int curMax = getMax(n - depth - 1);
        for(int i = value * 2; i <= curMax; i++) {
            comb(depth + 1, i);
        }
    }
}

정답 풀이

[i][j]의 개수는 [i - 1][j / 2]까지의 개수를 다 합친것과 같다는 것을 이용해서 풀이합니다.

  • 모듈러 연산의 특성
import java.util.Scanner;
 
public class Main {
    public static final int Div = 1000000007;
    public static final int MAX_M = 2001;
    public static final int MAX_N = 11;
 
    public static int n, m;
    public static long[][] dp = new long[MAX_N][MAX_M];
 
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
 
        n = sc.nextInt(); // n개를 발급 받음
        m = sc.nextInt(); // m까지의 수를 입력 받음
 
        // 초기 조건 설정: 첫 번째 열의 모든 값을 1로 설정합니다.
        for (int j = 1; j <= m; j++)
            dp[1][j] = 1;
 
        // dp 배열을 채웁니다.
        for (int i = 2; i <= n; i++) {
            for (int j = m; j >= 1; j--) {
                // Java는 빈 int 배열을 선언하면 0으로 초기화됨
                // dp[i][j] = 0;
                for (int k = j / 2; k >= 1; k--) {
                    dp[i][j] = (dp[i][j] + dp[i-1][k]) % Div;
                }
            }
        }
 
        // 최종 결과를 계산합니다.
        long result = 0;
        for (int j = m; j >= 1; j--) {
            result = (result + dp[n][j]) % Div;
        }
 
        // 결과를 출력합니다.
        System.out.println(result);
    }
}