BOJ [1011] Fly me to the Alpha Centauri

2017. 8. 10. 18:27· 알고리즘

https://www.acmicpc.net/problem/1011



시작점 x부터 도착점 y까지 이동하는 문제. 이동 횟수를 구해야 한다.

이동 속도는 1부터 시작하고, 한 번 이동할 때마다 ±1씩 증감한다.

마지막 지점에 들어오는 속도는 반드시 1이 되어야 한다는 조건이 있다.

즉, 속도는 1씩 증가하여 중간 지점에서 최대치에 도달한 후 서서히 감소하여 다시 1로 돌아온다.

규칙을 찾아보기 위해 표로 정리해 보았다.


두 지점 사이의 거리 최적의 속도 변화
1 1
2 11
3 111
4 121
5 1211
6 1221
7 11221
8 12221
9 12321
10 112321
11 122321
12 123321
... ... 



1번 이동 : 1항부터
2번 이동 : 2항부터
3번 이동 : 3항부터
4번 이동 : 4항부터
5번 이동 : 7항부터
. . .

위 결과를 항으로 정리한다.

A1 = 1
A2 = 2    (1항에서 1 증가)
A3 = 3    (2항에서 1 증가)   
A4 = 5    (3항에서 2 증가)
A5 = 7    (4항에서 2 증가)
A6 = 10  (5항에서 3 증가)
...
An+1 = An  +  | n/2 |


규칙만 알아낸다면 코드 작성은 간단하다.


#include <cstdio>

int main()
{
	int T;

	scanf("%d", &T);
	while (T--)
	{
		int x, y, ans = 1;
		unsigned int gap, pos = 1;
		scanf("%d %d", &x, &y);
		gap = y - x; // 두 지점 사이의 거리
		for (int i = 2; pos < gap; i++)
		{
			pos += i / 2; // pos는 현재 위치이며 gap보다 작아야 한다.
			ans++;
		}
		if (pos > gap)
			ans--;
		printf("%d\n", ans);
	}
	return 0;
}


'알고리즘' 카테고리의 다른 글

BOJ [1676] 팩토리얼 0의 갯수  (0) 2017.08.10
BOJ [1874] 스택 수열  (0) 2017.08.10
BOJ [3344] N-Queen  (0) 2017.08.10
BOJ [1463] 1로 만들기  (0) 2017.08.10
BOJ [6588, 9020] 골드바흐의 추측  (0) 2017.08.10
'알고리즘' 카테고리의 다른 글
  • BOJ [1874] 스택 수열
  • BOJ [3344] N-Queen
  • BOJ [1463] 1로 만들기
  • BOJ [6588, 9020] 골드바흐의 추측
감동이중요해
감동이중요해
https://github.com/dhmin5693 dhmin5693@naver.com
감동이중요해
티끌모아 산을 쌓아보자
감동이중요해
전체
오늘
어제
  • 분류 전체보기 (111)
    • 알고리즘 (35)
    • Infra & Dev tools (10)
      • Git (2)
      • Cloud platform (5)
      • Mac, Linux (3)
    • BigData (1)
    • IT 도서 (11)
      • Clean Code (8)
    • Java (36)
      • Spring framework (19)
      • JPA (5)
      • Domain Driven Design (3)
    • Database (2)
      • oracle (1)
      • mysql (0)
    • Computer Science (7)
      • 운영체제 (7)
    • 기타 (9)
      • 크롤링(파이썬) (1)
      • 회고 (4)
      • Career (0)

블로그 메뉴

  • 홈
  • 태그
  • 미디어로그
  • 위치로그
  • 방명록

공지사항

  • About me

인기 글

태그

  • 영속
  • Mac
  • 알고리즘
  • Clean Code
  • Linux
  • 회고
  • Java
  • DDD
  • Database
  • 운영체제
  • Stream
  • bean
  • JPA
  • AWS
  • 우아한테크캠프2기
  • 영속상태
  • 블라인드공채
  • 메모리
  • Spring
  • 프로세스

최근 댓글

최근 글

hELLO · Designed By 정상우.v4.2.2
감동이중요해
BOJ [1011] Fly me to the Alpha Centauri
상단으로

티스토리툴바

개인정보

  • 티스토리 홈
  • 포럼
  • 로그인

단축키

내 블로그

내 블로그 - 관리자 홈 전환
Q
Q
새 글 쓰기
W
W

블로그 게시글

글 수정 (권한 있는 경우)
E
E
댓글 영역으로 이동
C
C

모든 영역

이 페이지의 URL 복사
S
S
맨 위로 이동
T
T
티스토리 홈 이동
H
H
단축키 안내
Shift + /
⇧ + /

* 단축키는 한글/영문 대소문자로 이용 가능하며, 티스토리 기본 도메인에서만 동작합니다.