Skip to content
kkw
조회 수 33 추천 수 0 댓글 0
?

단축키

Prev이전 문서

Next다음 문서

크게 작게 위로 아래로 댓글로 가기 인쇄 첨부
?

단축키

Prev이전 문서

Next다음 문서

크게 작게 위로 아래로 댓글로 가기 인쇄 첨부

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

 

 

 

문제요약:

x지점에서 부터 y지점까지 매번 k, k-1, k+1 으로 이동 할 수 있다 가정 했을때 최소한의 횟수로 이동하여라! 단, 처음과 마지막 이동은 1 만큼만 이동할 수 있다. 

 

 

알고리즘:

 

처음에는 그라디 알고리즘 문제를 풀듯이 매번 선택지에서 가장 거리를 줄일수 있는 선택지를 선택하는 방식으로 문제를 풀었다 백준에서 예제로 준 문제도 잘 출력되길레 성공을 확신했으나

결과는 시간초과 ㅜㅜ 시간초과 죽었으면...    후에 안 사실이지만 알고리즘 또한 틀렸다...

 

1)우선 x와 y좌표간의 이동하는 거리의 총량이 중요하므로 우선 거리를 구하기 위해 y-x를 해준다.

 

2) 규칙을 찾는다  

 

아래의 표는 거리에 따른 항로와 공간이동장치 회수를 표로 나타낸것이다

 

 

거리

항로

이용횟수

1

1

1

2

1-1

2

3

1-1-1

3

4

1-2-1

3

5

1-2-1-1

4

6

1-2-2-1

4

7

1-2-2-1-1

5

8

1-2-2-2-1

5

9

1-2-3-2-1

5

10

1-2-3-2-1-1

6

11

1-2-3-2-2-1

6

12

·

6

13

·

7

14

·

7

15

·

7

16

1-2-3-4-3-2-1

7

 

 

위의 표에서 눈치챘겠지만 다음과 같은 규칙이 나온다!

 

 

제곱

항로

회수

1

1

1

4

1-2-1

3

9

1-2-3-2-1

5

16

1-2-3-4-3-2-1

7

 

이를 통해서 이동하는 거리의 총량이 n의 제곱과 같을때

최소한의 이용횟수는 2*n-1이란 공식이 만들어진다!

 

항로.PNG

 

위 표를 통해서 dist-n<=x<=n*n 까지는 2*n-1이 되고  범위에 포함하지 않는 수는 2*n-2 공식이 성립한다.

 

개인적으로 내가 푼 문제중에서 가장 어려웠다 ㅜㅜ 이 문제를 푸는데 대략 2~3시간 정도 걸린것 같다.

막상 성공한 소스코드를 보니깐 허무? 하기도 하고 규칙을 막상 찾으니깐 이런 쉬운 문제를 왜이리 오래걸렸을까 ㅋㅋㅋ 

 

<성공 소스코드>

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#include<iostream>
 
using namespace std;
 
int dt(int dist)
{
    long long i=1;
 
 
    while (i * i <= dist)i++;
 
    if ((i-1)*(i-1== dist)
        return 2*(i-1- 1;
    else if ((i*i-i)+1 <=dist)
        return 2 * i - 1;
    else
        return 2 * i - 2;
 
 
}
 
int main()
{
    int x,y;
    int t;
    int num;
    
    cin >> t;
    
    while(t--)
    {
        cin >> x >> y;
        num=dt(y - x);
        cout << num<<"\n";
    }
}
cs

 

 

<문제를 풀다 장렬히 사망한 소스코드들>

 

(그라디 알고리즘으로 시도)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
#include<iostream>
 
using namespace std;
 
int num[100000];
int ho = 0;
 
void warp(int dis)
{
    int k = 1, sk, bk;
    int cnt = 0;
 
    while (0 != dis)
    {
        cnt++;
        sk = k - 1;
        bk = k + 1;
 
        if (0 <= (dis - bk))
        {
            dis -= bk;
            k = bk;
        }
        else if (0 <= dis - k)
            dis -= k;
        else
        {
            dis -= sk;
            k = sk;
        }
    }
    
        num[ho] = cnt + 2;
        ho++;
}
 
 
int main()
{
    int repeat;
    int x, y;
    cin >> repeat;
 
    for (int i = 0; i < repeat; i++)
    {
        cin >> x >> y;
        warp((y - x) - 2);
    }
 
    for (int i = 0;i<repeat; i++)
    {
        cout << num[i]<<"\n";
    }
 
}
cs

 

 

<시간초과 오류>

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include<iostream>
 
using namespace std;
 
int dt(int dist)
{
    int i;
    int temp = 0;
 
    for (i = 0; temp < dist; i++)
        temp = i * i;
 
    if (temp == dist)
        return 2 * i - 3;
    else
        return 2 * i - 4;
 
 
}
 
int main()
{
    int x,y;
    int rep;
    int num;
    
    cin >> rep;
    
    for (int i=0 ;i<=rep; i++)
    {
        cin >> x >> y;
        num=dt(y - x);
        cout << num<<"\n";
    }
}
cs

 

 

 

?

List of Articles
번호 제목 글쓴이 날짜 조회 수
8 백준 2775번 부녀회장이 될테야! file kkw 2019.08.12 21
7 백준 10250번 ACM 호텔 kkw 2019.08.10 25
6 백준 2869번 달팽이는 올라라고 싶다 kkw 2019.08.07 32
» 백준 1011번 Fly me to the Alpha Centauri file kkw 2019.08.04 33
4 백준 1193번 분수찾기 문제 file kkw 2019.08.03 30
3 백준2292번 벌집 문제 file kkw 2019.08.01 27
2 백준 2839번 설탕배달 문제 file kkw 2019.07.31 25
1 백준1712번 손익분기점 풀이과정 1 kkw 2019.07.29 27
Board Pagination Prev 1 Next
/ 1

Powered by Xpress Engine / Designed by Sketchbook

sketchbook5, 스케치북5

sketchbook5, 스케치북5

나눔글꼴 설치 안내


이 PC에는 나눔글꼴이 설치되어 있지 않습니다.

이 사이트를 나눔글꼴로 보기 위해서는
나눔글꼴을 설치해야 합니다.

설치 취소