글 읽기 - 1011 번 JAVA 답 오류 [반례 부탁드립니다]

scs9802 3년 전 0

저는 계수정렬의 일반항을 이용하여 구하였습니다.

https://www.acmicpc.net/board/view/26059

나오는 예제는 올바른 값이 나옵니다.

그런데 한가지 이상한게

0 15 를 입력하게 되면 6이 출력되어야 하는것이 아닌가요?

이동해야 하는 거리 = 15

처음의 이동거리는 무조건 1 -> 0+1 = 1

0,1,2 중에서 2만큼 이동 2 -> 1+2 = 3

1,2,3 중에서 3만큼 이동 3 -> 3+3 = 6

2,3,4 중에서 4만큼 이동 4 -> 6+4 = 10

3,4,5 중에서 5만큼 이동 5 -> 10+5 = 15 [마지막은 무조건 1만큼 이동해야 하므로 조건성립 X]

3,4,5 중에서 4만큼 이동 5 -> 10+4 = 14

마지막의 이동거리 6 -> 14+1 = 15

즉 최소이동횟수는 6번 아닌가요?

그런데 링크에 있는 예제에서의 답은 최소이동횟수가 7번 이라고 나옵니다.

import java.util.*;
public class Baekjoon_1011 {
    static int check = 0;
    public static void main(String[] args)
    {
        Scanner sc = new Scanner(System.in);
        int t = sc.nextInt();
        long x,y,dst,number,sum=0;
        int i,j,k,count;
        for(i=0;i<t;i++)
        {
            check=0;
            count = 0;
            dst = 1; //가장 처음 이동 거리는 1광년만 가능
            x = sc.nextLong(); //출발 지점
            y = sc.nextLong(); //도착 지점
            if(x>=0 && y>=0 && x<y &&y<Math.pow(2,31))
            {
                dst = (y-1)-x;
                sum = a(dst);
                number = find_n(sum);
             //   System.out.println("number >> "+number);
                if((y-x) == 1) {
                    number = 1;

                }
                else if(dst == 1)
                {
                    number = 2;

                }
                else if(check==1)
                {
                    number = number;
                }
                else if(check==2)
                {
                    number -= 1;
                }
                else if(number == 1 || (1+number) < (dst))
                {
                    number += 2;
                }
                else if((1+number) == (dst))
                {
                    number++;
                }
                System.out.println(number);

            } else
                return;

        }
    }
    public static long find_n(long input)
    {
        int i=1,j=1;
        long uni=0;
        while(true) {
            uni = i * (i + 1);
          //  System.out.println("input >> " + input);
          //  System.out.println("uni >> " + uni);
            if (uni == input) {
                return i;
            } else if (uni > input) {
                return i - 1;
            } else if (uni<0) { // Y의 값이 MAX값 일 경우
            //    System.out.println("i >> "+(i));

                if(Integer.toUnsignedLong(i*(i-1)*2) > input) {
                  //  System.out.println((i-1)*2);
                    check++;
                    return (i - 1) * 2;
                }
                else {
                  //  System.out.println((i)*2);
                    check = 2;
                    return (i) * 2;
                }

            }
            i++;
        }
    }
    public static long a(long input)
    {
        long sum,n;
        sum = 2*(input-1)+2;
        return sum;
    }
    
}

joe2357 3년 전 1

1 2 3 4 4 다음에 1이 올 수 없습니다. 내려가는 것도 1씩 내려가야 하기 때문이죠.

0 15에서의 정확한 답은 1 2 3 3 3 2 1로 7번 이동해야 합니다.

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

문제

문제

출처

ICPC

1011 번 JAVA 답 오류 [반례 부탁드립니다]

scs9802 3년 전 0

joe2357 3년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말