문제
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);
}
}