글 읽기 - 반례 좀 찾아주세요..ㅠㅠ

ljo950924 4년 전 0

제출 결과 틀렸습니다 가 나오는데

반례를 못 찾겠습니다..

어디가 잘못됐는지 혹은 반례라도

알려주실 수 있을까요..?

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
	static int n;
	static long[] factorial;
	static int[] used;
	
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		n = Integer.parseInt(br.readLine());
		
		StringTokenizer st = new StringTokenizer(br.readLine());
		// 문제 번호
		int q = Integer.parseInt(st.nextToken());
		
		// 수열 찾기
		if(q == 1) {
			long k = Long.parseLong(st.nextToken());
			factorial = new long[n+1];
			used = new int[n+1];
			
			make(n,k);
		}
		
		// 번호 찾기
		else if(q == 2) {
			int[] numbers = new int[n+1];	
			for(int i=n; i>=1; i--) {
				numbers[i] = Integer.parseInt(st.nextToken());
			}
			factorial = new long[n+1];
			used = new int[n+1];
			
			long rank=0;
			for(int i=n; i>=1; i--) {
				rank += find(i, numbers[i]);
			}
			
			System.out.println(rank);
		}
	}
	
	static long factorial(int n) {
		if(n==0 || n==1) return 1;
		
		if(factorial[n] != 0) return factorial[n];
		
		return factorial[n] = n * factorial(n-1);
	}
	
	// 1번 문제
	static void make(int pos, long k) {
		long tmp = factorial(pos-1);
		
		if(tmp>k) {
			for(int i=1; i<=n; i++) {
				if(used[i] == 0) {
					System.out.print(i+" ");
					used[i] = 1;
					break;
				}
			}
			make(pos-1, k);
		}
		else if(tmp==k) {
			for(int i=1; i<=n; i++) {
				if(used[i] == 0) {
					System.out.print(i+" ");
					used[i] = 1;
					break;
				}
			}
			for(int i=n; i>=1; i--) {
				if(used[i] == 0) {
					System.out.print(i+" ");
					used[i] = 1;
				}
			}
		}
		else if(tmp<k) {
			long count  = k/tmp;
			
			for(int i=1; i<=n; i++) {
				if(used[i] == 1) continue;
				
				if(count == 0) {
					System.out.print(i+" ");
					used[i] = 1;
					make(pos-1, k%tmp);
					break;
				}
				else{
					count--;
				}
			}
			
			for(int i=n; i>=1; i--) {
				if(used[i]==1) continue;
				
				System.out.print(i+" ");
				used[i]=1;
			}
			//make(pos-1, k%tmp);
		}
	}
	
	// 2번 문제
	static long find(int pos, int val) {
		if(val==1) {
			used[1] = 1;
			return 0;
		}
		if(pos==1) {
			return 1;
		}
		
		long tmp = factorial(pos-1);
		
		long ret=0;
		for(int i=1; i<val; i++) {
			if(used[i]==1) continue;
			
			ret += tmp;
		}
		
		used[val] = 1;
		return ret;
	}
}

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

문제

문제

출처

ICPC

반례 좀 찾아주세요..ㅠㅠ

ljo950924 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말