항 전 OJ (HDOJ) 1865 문제: 1sting (대수 조작 - Fibonacci 수열)

제목:
길이 가 200 을 넘 지 않 는 서열 을 제시 합 니 다. 이 서열 은 숫자 1 로 만 구성 되 고 두 가지 조작 만 할 수 있 습 니 다. 1, 2 개 1 을 합 쳐 2, 2, 이동 1 과 2 의 위치 로 합 칠 수 있 습 니 다.예 를 들 어 길이 가 4 인 서열 1111 은 상기 두 가지 조작 을 거 친 후에 다음 과 같은 5 가지 서로 다른 새로운 서열 1111, 121, 112, 211, 22 를 얻 을 수 있다.먼저 정수 n (테스트 실례 횟수 표시) 을 입력 하고 매번 길이 가 200 을 초과 하지 않 는 서열 을 입력 하여 서로 다른 배열 의 개 수 를 구한다.
예제 입력:
3 1 11 11111
예제 출력:
1 2 8
해결 방안:
int 형 을 사용 하면 경 계 를 넘 고 멍청하게 double 로 저장 하 는데 WA 를 발견 한 후에 게 으 름 을 피 우 는 것 도 초학 이 라 고 할 수 있 습 니 다. 자바 의 여러 가지 유형 을 사 용 했 습 니 다. 간단 합 니 다. 쓰기 전에 자바 documentation 을 찾 아 보 았 습 니 다.입력 길이 가 200 일 때 그 결 과 는 453973694165307953197969697469710619233826 이 어야 한다.늙 었 다.하지만 수 조 는 201 까지 가 야 한다. 200 까지 가면 WA 다.HDOJ 1715 문제 도 이 문제 다.
첨부: Java 1.7 API
import java.math.*;
import java.util.Scanner;
public class Main {
    public static void main(String args[])    {
        Scanner input = new Scanner(System.in);
        BigInteger arr[]= new BigInteger[201];//      
        int i;
        String str;
        arr[0]=new BigInteger("1");//   
        arr[1]=new BigInteger("2");        
        for(i=2;i<201;i++)//  fibnacci
            arr[i]=arr[i-1].add(arr[i-2]);        
        i=input.nextInt();
        while(i>0)
        {
            str=input.next();            
            System.out.println(arr[str.length()-1]);
            i--;
        }
        
    }

}

좋은 웹페이지 즐겨찾기