[BOJ]2758宝くじ
21304 ワード
🔗 Problem
https://www.acmicpc.net/problem/2758
👩💻 Code - Dynamic Programming package baekjoon;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.StringTokenizer;
// 로또
public class BJ2758 {
static int t;
static int n;
static int m;
static long[][] dp;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
t = Integer.parseInt(br.readLine());
StringTokenizer st;
for(int i = 0; i < t; i++) {
st = new StringTokenizer(br.readLine());
n = Integer.parseInt(st.nextToken());
m = Integer.parseInt(st.nextToken());
dp = new long[n+1][m+1];
solution();
}
}
private static void solution() {
for(int i = 1; i <= m; i++) {
dp[1][i] = 1;
}
for(int i = 2; i <= n; i++) {
for(int j = 2; j <= m; j++) {
if(j%2 == 0) {
dp[i][j] = dp[i][j-1] + dp[i-1][j/2];
}
else {
dp[i][j] = dp[i][j-1];
}
}
}
long cnt = 0;
int start = (int)Math.pow(2, n-1); // n번째 고르는 수 중 가장 작은 값
for(int i = start; i <= m; i++) {
cnt += dp[n][i];
}
System.out.println(cnt);
}
}
👩💻 Code - Back Tracking package baekjoon;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.StringTokenizer;
// 로또
/* Back Tracking으로 구현하면 백준에서는 시간 초과 발생
DP로 해결하였음 */
public class BJ2758_2 {
static int t;
static int n;
static int m;
static int cnt;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
t = Integer.parseInt(br.readLine());
StringTokenizer st;
for(int i = 0; i < t; i++) {
st = new StringTokenizer(br.readLine());
n = Integer.parseInt(st.nextToken());
m = Integer.parseInt(st.nextToken());
cnt = 0;
backTracking(0, 0);
System.out.println(cnt);
}
}
private static void backTracking(int depth, int idx) {
if(depth == n) {
cnt++;
return;
}
if(idx * 2 <= m) { // isPromising() 조건
for(int i = idx*2; i <= m; i++) {
if(depth == 0 && i == 0) continue;
backTracking(depth + 1, i);
}
}
else return;
}
}
💡 Learned 아이디어
package baekjoon;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.StringTokenizer;
// 로또
public class BJ2758 {
static int t;
static int n;
static int m;
static long[][] dp;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
t = Integer.parseInt(br.readLine());
StringTokenizer st;
for(int i = 0; i < t; i++) {
st = new StringTokenizer(br.readLine());
n = Integer.parseInt(st.nextToken());
m = Integer.parseInt(st.nextToken());
dp = new long[n+1][m+1];
solution();
}
}
private static void solution() {
for(int i = 1; i <= m; i++) {
dp[1][i] = 1;
}
for(int i = 2; i <= n; i++) {
for(int j = 2; j <= m; j++) {
if(j%2 == 0) {
dp[i][j] = dp[i][j-1] + dp[i-1][j/2];
}
else {
dp[i][j] = dp[i][j-1];
}
}
}
long cnt = 0;
int start = (int)Math.pow(2, n-1); // n번째 고르는 수 중 가장 작은 값
for(int i = start; i <= m; i++) {
cnt += dp[n][i];
}
System.out.println(cnt);
}
}
👩💻 Code - Back Tracking package baekjoon;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.StringTokenizer;
// 로또
/* Back Tracking으로 구현하면 백준에서는 시간 초과 발생
DP로 해결하였음 */
public class BJ2758_2 {
static int t;
static int n;
static int m;
static int cnt;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
t = Integer.parseInt(br.readLine());
StringTokenizer st;
for(int i = 0; i < t; i++) {
st = new StringTokenizer(br.readLine());
n = Integer.parseInt(st.nextToken());
m = Integer.parseInt(st.nextToken());
cnt = 0;
backTracking(0, 0);
System.out.println(cnt);
}
}
private static void backTracking(int depth, int idx) {
if(depth == n) {
cnt++;
return;
}
if(idx * 2 <= m) { // isPromising() 조건
for(int i = idx*2; i <= m; i++) {
if(depth == 0 && i == 0) continue;
backTracking(depth + 1, i);
}
}
else return;
}
}
💡 Learned 아이디어
package baekjoon;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.StringTokenizer;
// 로또
/* Back Tracking으로 구현하면 백준에서는 시간 초과 발생
DP로 해결하였음 */
public class BJ2758_2 {
static int t;
static int n;
static int m;
static int cnt;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
t = Integer.parseInt(br.readLine());
StringTokenizer st;
for(int i = 0; i < t; i++) {
st = new StringTokenizer(br.readLine());
n = Integer.parseInt(st.nextToken());
m = Integer.parseInt(st.nextToken());
cnt = 0;
backTracking(0, 0);
System.out.println(cnt);
}
}
private static void backTracking(int depth, int idx) {
if(depth == n) {
cnt++;
return;
}
if(idx * 2 <= m) { // isPromising() 조건
for(int i = idx*2; i <= m; i++) {
if(depth == 0 && i == 0) continue;
backTracking(depth + 1, i);
}
}
else return;
}
}
아이디어
틀렸습니다
Reference
この問題について([BOJ]2758宝くじ), 我々は、より多くの情報をここで見つけました https://velog.io/@ssoyeong/BOJ-2758-로또テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol