글 읽기 - 1010 다리 놓기 . 뭐가 틀린걸까요?

skeksk 9년 전 0

다리끼리 교차해선 안된다는 문제를

동쪽에 총 m개의 다리를 A = {1,2,3,4 ...m} 수열로 생각하고

서쪽에 n개의 다리를 길이 n인 수열로 생각해서

A 수열에 길이가 n이면서 오름차순으로 선택할 수 있는 경우를 구하려고했습니다

ㅠㅠ 쉽게 해결되지 않네요 . 예제는 성공했으나 틀렸다고나옵니다.. 다른데이터 테스트하기도 쉽지두 않구 힘드네요!

​import java.util.Scanner;
public class Main{

static int n,m;

static int cache[][] = new int[35][35];

public static void main(String args[]){

Scanner in = new Scanner(System.in);

int t = in.nextInt();

while(t-->0){

n = in.nextInt();

m = in.nextInt();

System.out.println(f(0,n));

}

}
static int f(int now, int left){   //now : 현재 선택한 원소  , left : 남은 원소의 수

int sum=0;

if(cache[now][left] != 0)

return cache[now][left];

if(left == 0)

return 1;

for(int i=now+1; i<=m-left+1; i++)

sum += f(i,left-1);

return cache[now][left] = sum;

}

}

joonas 9년 전 1

다리끼리 교차하고 n, m이 나오는건... 1010 다리 놓기 아닌가요?

skeksk 9년 전 0

joonas님 감사합니다!! ㅋㅋㅋ 실수했네요..
흑흑 누구 아시는분있나용 능력자분들..

joonas 9년 전 0

음.. 이거 @baekjoon님이 쉬운 다이나믹 문제집에 추가하셨던데, 전 조합론으로 풀어서 ㅎㅎ..

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

1010 다리 놓기 . 뭐가 틀린걸까요?

skeksk 9년 전 0

joonas 9년 전 1

skeksk 9년 전 0

joonas 9년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말