[C언어] 백준 1011번 Fly me to the Alpha Centauri

 

• 문제 자체를 잘못 이해해 질문 게시판에 있는 팁 정리 글을 보고 겨우겨우 풀었다.
• 문제 접근
  • 처음 이동 거리는 1, 이후 012 중 선택, 가장 멀리 2를 가기로 했다면 다음 가능한 이동 거리는 123이 된다.
  • 맨 처음 이동 거리가 1로 시작했듯, 마지막 턴의 이동 거리도 1로 끝나야 한다.
    • 따라서 최소한의 이동횟수를 통해 움직이려면 점차적으로 증가해야 할 뿐만 아니라, 점차적으로 감소시켜야 한다.
    • 1 2 3 4 5 ... n ... 5 4 3 2 1 같은 패턴으로 이동한다.
    • sqrt를 사용한 풀이법이 있었으나.. 나는 일단 문제부터 풀고 공부를 해야 할 것 같아 반복문을 통해 풀었다.
      패턴을 파악하기 위해 열심히 끄적여봤다. 
  • (0 ≤ x < y < 2^31)
    • 2^31-1은 2147483647로, 32비트 정수에서 표현할 수 있는 가장 큰 수이다.
      그리고 공교롭게도 이는 int의 기본형 signed long int가 표현할 수 있는 가장 큰 수이다.
    • 즉 y의 값을 더하는 변수나 변수 y에 다른 값이 더해진다면 overflow를 막기 위해
      int가 아닌 최소 unsigned int로 변수를 선언해야 한다.
      그렇지 않으면 ... 값이 왜곡되어 반복문이 꼬이고 답 자체도 틀릴 뿐더러 시간초과 결과를 얻게 된다.

 

이동횟수를 증가시켜야 하는 거리와 증가분 패턴

총거리 (y-x)	거리 증가분 (a)	이동 횟수 (moves)	moves	a
1	1	1	2a-1	(m+1) / 2
2	1	2	2a	m / 2
3	2	3	2a-1	(m+1) / 2
5	2	4	2a	m / 2
7	3	5	2a-1	(m+1) / 2
10	3	6	2a	m / 2
13	4	7	2a-1	(m+1) / 2
17	4	8	2a	m / 2
21	5	9	2a-1	(m+1) / 2
26	5	10	2a	m / 2

• 1~26까지 패턴을 파악한 후 이동 횟수가 증가하는 경우들만 다시 도출해낸 표이다.
• 거리증가분이 일정하게 증가한다.
  • m = 2a-1 (홀수) 혹은 2a (짝수)
  • a = (m+1)/2 (홀수) 혹은 m/2 (짝수)
• 목표지점 y에서 현위치 x를 뺀 거리
  y-x > a의 총합을 만족하는 마지막 반복횟수 (moves, 이동횟수)가 문제가 요구하는 최종 값이다.
  • 예를 들어 총거리가 15라면 이동횟수는 7에 걸치게 된다.
    13~16(<17)까지의 거리는 7번만에 이동이 가능하다.
    *이해가 안가면 아래 표를 참고한다.
    
    
  • 변수를 최소화하기 위해 x를 현재 위치로 두고 이동할때마다 x를 증가시켰다.
    이에 따른 반복문의 조건은 y > x이다.
  • 앞서 얘기했듯 x는 계속해서 증가하기 때문에 y값이 2147483647(최대값)으로 주어졌을 때,
    마지막 반복에서 x는 증가분을 반영해 2147483647와 같아지거나 초과하게 된다.
    따라서 x는 unsinged int로 선언해야 하는데, 
    어차피 y, moves도 연산 과정에서 unsigned int로 casting될 것 같아 함께 같은 자료형으로 선언했다.

 

풀이1

#include <stdio.h>

int main(void)
{
	int T;
	unsigned int x, y, moves;

	scanf("%d", &T);
	while (T--)
	{
		scanf("%d %d", &x, &y);
		for (moves = 0; y > x; moves++)
			x += moves % 2 ? (moves + 1) / 2 : moves / 2;
		moves--;

		printf("%d\n", moves);
	}

	return 0;
}

 

코드 길이 자체는 짧고 간단해서 좋은데 사실 for문을 사용해서 푸는 이상, 최대 92681번까지 반복문이 돌게 된다.

그 결과 메모리 1112KB, 소요 시간은 4ms

이걸 줄이려면 sqrt 함수를 써서 풀어야 할 것 같다.

 

 

거리별 이동 패턴 및 이동횟수 그외 분석 [참고용]

거리 y-x	이동 패턴	이동 횟수	s (int) sqrt(y-x)	거리 - s^2	이동 횟수
1	1	1	1	0	2s-1
2	1 1	2	1	1	2s
3	1 1 1	3	1	2	2s+1
4	1 2 1	3	2	0	2s-1
5	1 2 1 1	4	2	1	2s
6	1 2 2 1	4	2	2	2s
7	1 2 2 1 1	5	2	3	2s+1
8	1 2 2 2 1	5	2	4	2s+1
9	1 2 3 2 1	5	3	0	2s-1
10	1 2 3 2 1 1	6	3	1	2s
11	1 2 3 2 2 1	6	3	2	2s
12	1 2 3 3 2 1	6	3	3	2s
13	1 2 3 3 2 1 1	7	3	4	2s+1
14	1 2 3 3 2 2 1	7	3	5	2s+1
15	1 2 3 3 3 2 1	7	3	6	2s+1
16	1 2 3 4 3 2 1	7	4	0	2s-1
17	1 2 3 4 3 2 1 1	8	4	1	2s
18	1 2 3 4 3 2 2 1	8	4	2	2s
19	1 2 3 4 3 3 2 1	8	4	3	2s
20	1 2 3 4 4 3 2 1	8	4	4	2s
21	1 2 3 4 4 3 2 1 1	9	4	5	2s+1
22	1 2 3 4 4 3 2 2 1	9	4	6	2s+1
23	1 2 3 4 4 3 3 2 1	9	4	7	2s+1
24	1 2 3 4 4 4 3 2 1	9	4	8	2s+1
25	1 2 3 4 5 4 3 2 1	9	5	0	2s-1
26	1 2 3 4 5 4 3 2 1 1	10	5	1	2s

• 거리가 제곱근 수 일 때
  • 최적 이동 패턴은 1 2 3 ... n ... 3 21
    • 총 이동 거리 y-x = n(n+1) + n(n-1) = n^2
    • y-x == (int) sqrt(y-x)의 제곱
      • y-x를 제곱근한 값이 정수이기 때문에 캐스팅 후에도 값은 변함없음.
      • 즉 거리의 제곱근을 버림하고 다시 제곱해도 같은 값
      • 거리 -s^2 == 0
  • 이동 횟수는 2n-1 = 2 * sqrt(y-x) -1 = 2s-1
• 거리가 제곱근 수가 아니고, 거리 - s^2이 s보다 작거나 같을 때
  • 이동횟수는 2n-1 + 1 = 2 * sqrt(y-x) =  2s
• 거리가 제곱근 수가 아니고, 거리 -s^2이 s보다 클 때
  • 이동횟수는 2n-1 + 2 = 2 * sqrt(y-x) + 1 =  2s+1

 

풀이2

#include <stdio.h>
#include <math.h>

int main(void)
{
	int T, x, y, s;

	scanf("%d", &T);
	while(T--)
	{
		scanf("%d %d", &x, &y);
		s = (int) sqrt(y - x);

		if (s * s == y - x)
			printf("%d\n", 2 * s - 1);
		else if (s >= (y-x) - (s*s))
			printf("%d\n", 2 * s);
		else
			printf("%d\n", 2 * s + 1);
	}

	return 0;
}

메모리는 1128KB, 소요 시간은 0MS

sqrt 함수를 사용하기 때문에 메모리가 늘어난 걸까? 잘 모르겠다.

 

 

 

이건 다른 사람 코드를 살짝 수정해본 건데, 사후적으로는 코드가 이해가 가는데...

문제만 보고 패턴을 어떻게 발견할 수 있을까싶다.

 

#include <stdio.h>

int main(void)
{
	int T, x, i;
	unsigned int y; //overflow방지
	scanf("%d", &T);
	while(T--)
	{
		scanf("%d %lu", &x, &y);
		for (i = 1; i * i < y - x; i++)
			;
		i--;
		printf("%d\n", i * i + ((i+1) * (i+1) - i * i) / 2 >= y - x ? i * 2 : (i+1) * 2 - 1);
	}

	return 0;
}