백준 1011 Fly me to the Alpha Centauri

문제 링크

1011번: Fly me to the Alpha Centauri

이 문제는 1년전에 풀어봤던 문제인데 이 때도 정말 고민하고 생각하면서 겨우 풀었던 것으로 기억한다. 근데 이번에는 풀다가 도저히 생각이 안나서 작년에 내가 푼 문제를 보았다. 쓰레기 짜식..... 할튼 알고보니? 쉬운 문제였다. 

 

이 문제의 경우의 수를 잘 생각해보면 아래와 같이 나올 수 있다. 

거리	방법
3	1 1 1
4	1 2 1
5	1 2 1 1
8	1 2 1 2 1

 

잘보면 좌우대칭이 발생하는 것을 확인할 수 있다. 그래서 나의 경우에는 시작점은 더해주고 최종점은 마이너스 해주는 방식으로 대칭적으로 만들어주었다. 그 후 시작점과 종료점이 교차된다면 그대로 count한 것을 출력. 또는 움직일 수 있는 거리랑 남은 거리가 같거나 커질 경우 +1을 해주면서 종료할 수 있다.

 

#include <cstdio>
#include <vector>
#define ll long long

using namespace std;

vector<int> movePoint;

int main(){
	ll T, x, y;
	scanf("%lld", &T);

	for(int i = 0; i < T; i++){
		scanf("%lld %lld", &x, &y);
		ll move = 1, count = 0;
		ll start = x, desination = y;

		while(1){
			ll diff = desination - start;
			if(start >= desination){	
				printf("%lld\n", count);
				break;
			}else if(move >= diff){
				printf("%lld\n", count+1);
				break;
			}

			start+= move, desination -= move;
			count += 2, move += 1;
		}
	}
}

 

 

안녕하세요 뱅둔입니다 :D

 

출발할 때 속도가 1 들어갈 때 속도가 1 이어야 하니까 속도 그래프? 가 산처럼 그려질꺼라 생각하고, 출발지와 도착지에서 출발시켜 정상에서 만나게 했습니다. 

num = int(input())
result=[]
for i in range(num):
    a, b = map(int, input().split())
    count=0
    dst = b-a
    k = 1
    p = 1
    while dst > 0:
        dst -= k
        k += 1
        if dst >= p:
            dst -= p
            p += 1
            count+=1
        count+=1

    result.append(count)
for j in result:
    print(j)

 

 

안녕하세요 IT19입니다 😎

 

위 사진과 같이 규칙을 보면 두 수의 차이를 보았을 때

제곱수(빨간 원)마다 새로운 숫자(초록 형광펜)가 나타나게 됩니다.

이 횟수는 오른쪽과 같이 (루트제곱 * 2) -1이 됩니다.

 

while문으로 두 수의 차이보다 작은 제곱수 중에서 가장 큰 값을 찾아준 다음에

(제곱수+1)부터 (제곱수+루트제곱수)까지의 횟수가 같고

루트제곱수*2, 다음 제곱수 - 1까지 횟수가 같으므로 적정한 위치를 찾아 값을 출력해줍니다.

import sys

t = int(sys.stdin.readline())
for i in range(t):
    x, y = map(int, sys.stdin.readline().split())
    space = y - x
    num = 1

    while True:
        if num ** 2 <= space < (num + 1)**2:
            break
        num += 1
    if num ** 2 == space:
        print((num * 2) - 1)
    elif num ** 2 < space <= num ** 2 + num:
        print(num * 2)
    else:
        print((num * 2) + 1)