Search Results for 'Algorithm'

52 POSTS

  1. 15:23:09 [PKU] 2590 Steps

[PKU] 2590 Steps

Posted 2008/07/24 15:23

수직선 상에 시작점과 끝점이 주어진다. 두 점의 위치를 알았을 때 두 점 사이를 이동하는 최소 스텝수를 구하여라.


규칙
  - 한 스텝 거리는 자연수로 이전 스텝 거리와 같거나 1만큼만 차이가 나야 한다.
  - 스텝의 처음과 마지막은 반드시 1이어야한다.

다음은 x Step으로 갈 수 있는 최대거리를 미리 계산해 본 것이다.

step   : 길이
0 step : 0
1 step : 1      (이전 Step + 1)
2 step : 2      (이전 Step + 1)   
3 step : 4      (이전 Step + 2)
4 step : 6      (이전 Step + 2)
5 step : 9      (이전 Step + 3)
6 step : 12     (이전 Step + 3)
.........

증가치가 꾸준히 1, 1, 2, 2, 3, 3, .. 식으로 1부터 차례대로 2개씩 나타나는 것을 알 수 있다.


// No.2590 Steps

import java.util.*;
import static java.lang.System.*;

public class Main {
        Scanner in = new Scanner(System.in);
       
        public Main() {
                int n = in.nextInt();
                for(int i=0 ; i<n ; i++) {
                        start();
                }
        }
       
        private void start() {
                int gapOfPoints = -1*in.nextInt() + in.nextInt();
               
                if(gapOfPoints == 0) {
                        out.println(0);
                        return;
                }
               
                int i=1;
                for(int gapOfTemp=0 ; gapOfTemp<gapOfPoints ; i++)
                        gapOfTemp += Math.ceil(i/2.0);
               
                out.println(--i);
        }
       
        public static void main(String[] args) {
                new Main();
        }
}

'C.S.E > Algorithm' 카테고리의 다른 글

[PKU] 2590 Steps  (0) 15:23:09
[PKU] 1028 Web Navigation  (0) 15:09:48
[PKU] 1218 The Drunk Jailer  (0) 2008/07/23
[PKU] 1003 Hangover  (0) 2008/07/23
PKU Judge Online 소개  (0) 2008/07/23
[ACM] Problem B. Editor  (0) 2008/07/12
« PREV : 1 : 2 : 3 : 4 : 5 : ... 52 : NEXT »