DRAGON 질문드립니다.

  • songmw725
    songmw725

    DRAGON 질문 드립니다.

    세대가 진화할 수록 늘어나는 길이를 미리 계산하였습니다.
    p-1 값 만큼 skip한 후, 그 이후부터 l길이 만큼 StringBuffer에 넣어서 출력하게 구현하였습니다.
    이런저런 테스트 케이스 널어 보고,
    경계값 50 1000000000 50 넣어 봤는데 잘 나오는것 같습니다.
    도움 부탁드립니다.

    package algospot;
    
    import java.io.BufferedReader;
    import java.io.IOException;
    import java.io.InputStreamReader;
    import java.util.Arrays;
    
    public class MainDragon {
        private static int n;
        private static StringBuffer sb;
        private static int skip;
        private static int l;
        private static long[] caches;
    
        public static void main(String[] args) throws NumberFormatException, IOException {
            BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
            precalc();
            int cases = Integer.parseInt(br.readLine());
            for (int i = 0; i < cases; i++) {
                String[] split = br.readLine().split(" ");
                n = Integer.parseInt(split[0]);
                skip = Integer.parseInt(split[1])-1;
                l = Integer.parseInt(split[2]);
                sb = new StringBuffer();
                curve("FX" , n);
                System.out.println(sb);
            }
        }
    
        private static void precalc() {
            caches = new long[51];
            caches[0] = 1;
            for (int i = 1; i <= 50; i++) {
                caches[i] = (long) (caches[i-1] + Math.pow(2, i+1) - Math.pow(2, i-1));
            }
        }
    
        private static void curve(String seed, int generation) {
            if(generation == 0) {
                if(l > 0) {
                    printSeed(seed);
                }
                return;
            }
            for (int i = 0; i < seed.length(); i++) {
                if(seed.charAt(i) == 'X') {
                    long length = caches[generation];
                    if (length <= skip) {
                        skip = (int) (skip -length);
                    } else {
                        curve("X+YF", generation - 1);
                    }
                } else if(seed.charAt(i) == 'Y') {
                    long length = caches[generation];
                    if (length <= skip) {
                        skip = (int) (skip -length);
                    } else {
                        curve("FX-Y", generation - 1);
                    }
                } else {
                    if(l >0) {
                        printSeed(String.valueOf(seed.charAt(i)));
                    } else {
                        return;
                    }
                }
            }
        }
    
        private static void printSeed(String seed) {
            if(skip>0) {
                if(seed.length() <= skip) {
                    skip = skip - seed.length();
                } else {
                    skip = 0;
                    printSeed(seed.substring(skip));
                }
            } else {
                for (int i = 0; i < seed.length() && l != 0; i++) {
                    sb.append(seed.charAt(i));
                    l--;
                }
            }
        }
    }
    

    8년 전
2개의 댓글이 있습니다.
  • hyunhwan
    hyunhwan

    2 9 2를 넣어보세요


    8년 전 link
  • songmw725
    songmw725

    @hyunhwan 헛 이런 오류가.. ㅎㅎ 답변감사합니다.


    8년 전 link
  • 정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.