글 읽기 - 어디가 잘못되었는지 모르겠습니다..

ljs921026 4년 전 0

이항계수를 사용하여 dp로 풀었습니다.

skip을 사용하여 첫번째 글자가 a혹은 z일 경우로 나눠 풀었습니다.

반례가 있을까요?

import java.util.*;
import java.io.*;

public class Main {
	static int[][] bino;
	static int n;
	static int m;
	static int k;
	
	public static void main(String[] args) throws IOException{
		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st=null;
		st=new StringTokenizer(br.readLine());
		n=Integer.parseInt(st.nextToken());
		m=Integer.parseInt(st.nextToken());
		bino=new int[n+m+1][n+m+1];
		bino();
		k=Integer.parseInt(st.nextToken());
		if(k>bino[n+m][n])
			System.out.println(-1);
		else
			System.out.println(d(n,m,k));
	}
	
	public static void bino() {
		for(int i=0;i<=n+m;i++) {
			bino[i][0]=1;
			bino[i][i]=1;
		}
		for(int i=2;i<=n+m;i++) {
			for(int j=1;j<i;j++) {
				bino[i][j]=bino[i-1][j-1]+bino[i-1][j];
			}
		}
	}
	
	public static String d(int n,int m,int k) {
		if(n==0) {//n을 다썼을 경우
			String ans="";
			for(int i=0;i<m;i++)
				ans+="z";
			return ans;
		}
		
		if(k<=bino[n+m-1][n-1])
			return "a"+d(n-1,m,k);
		else
			return "z"+d(n,m-1,k-bino[n+m-1][n-1]);
	}
}

ljs921026 4년 전 0

데이터 범위를 잘못 설정했네요. 해결했습니다.

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

문제

문제

출처

ICPC

어디가 잘못되었는지 모르겠습니다..

ljs921026 4년 전 0

ljs921026 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말