Baekjoon 1011번 Fly me to the Alpha Centauri

Baekjoon 1011번 Fly me to the Alpha Centauri

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


사실 이 문제를 처음에 잘못이해한 나머지 실수를 했는데

그것은 예로 들어 설명하자면 0 ~ 8사이의 숫자를 빠르게 가는 방법이라고 가정한다면

0 (+1) 1 (+2) 3 (+3) 6 (+4) 7 (+1) 8

이런식으로 해도된다는 잘못된 인식 때문에 큰 오류에 빠졌다.

그러나 다 알다시피 +4에서 3, 4, 5 중 하나를 선택할 수 있지 바로 +1은 불가능했다.

그래서 나온 잘못된 코딩은 아래와 같다.

getNum=int(input())

for i in range(getNum):
    start,end=input().split()
    val=int(end)-1-int(start)
    count=1
    before, after=0,0 

    while val > 0:
        if val == int(end)-1-int(start):
            before = 1
        else:
            if val >= after+1:
                before = after + 1

            elif after-1 < val <= after:
                before = after
            else:
                before=after-1
        after = before
        val -= before
        count += 1

    print(count)

그럼 올바른 코딩은 무엇일까

이것도 생각이 많아졌다. 그러나 최소한으로 움직이는 횟수를 구하는 문제라 그나마 쉬운 편에 속한 문제였다고 생각한다. 왜냐하면 횟수에 속하는 숫자의 개수를 구하는 문제가 아니기 때문에 간단하게 나타낼 수 있었기 때문이다.

우선 아이디어는 다음과 같다.

+1 +2 ⋯ +k ⋯ +k  ⋯ +2 +1의 방법을 나타내는데 k와 k 사이 숫자 간격이 어느정도냐에 따라 많은 것이 바뀔 것이다.

때문에 만약 +k와 +k 사이에 어떤 일이 일어나는지를 다양한 숫자를 써서 파악해본 결과

도출할 수 있었던 결론은

k와 k 사이의 간격이 k+1보다 작거나 같다면 개수는 2(k+1) -1개 이고

k와 k 사이의 간격이 k+1보다 크다면 개수는 2(k+1)개 이다.

사실 이렇게 생각하는 결론은 내부를 어떻게 구할래라고 물으면 차원이 다른 문제가 된다.
왜냐하면 간격에 따라 k와 k 사이의 간격이 k-1보다 더 작으면 더 넓혀서 k-1과 k-1 사이 간격을 배분하는 방법으로 확장해서 숫자를 세야하니까 말이다.

그러나 우리가 구하고자하는 것은 횟수이고 그것은 아래 코딩으로 답을 대신한다.

올바른 코딩으로 정리하면 아래와 같다.

getNum=int(input())

for i in range(getNum):
    start,end=map(int, input().split())
    val=end-start
    count=0
    improve=0
    tot=0

    while val > tot:
        improve += 1
        tot += 2*improve

    if val <= tot-improve:
        count = 2*improve -1
    else:
        count = 2*improve    

    print(count)

참고로 아래 숫자를 예시로 이해하는데 참고하길 바란다.

1) 0 ~ 13의 경우

0 (+1) 1 (+2) 3 (+3) 6 (+1) 7 (+3) 10 (+2) 12 (+1) 13 (불가능) 횟수 :7개
0 (+1) 1 (+2) 3 (+2) 5 (+3) 8 (+2) 10 (+2) 12 (+1) 13 (가능) 횟수 : 7개

저의 이론에 따르면 k=3이고 3과 3사이 간격은 1, 이 숫자는 k+1=4보다 작으므로
2(k+1)-1 = 2 *4 -1 =7개

2) 0 ~ 48의 경우

0 (+1) 1 (+2) 3 ⋯ (+6) 21 (+6) 27 (+6) 33 (+5) 38 (+4) 42 (+3) 45 (+2) 47 (+1) 48 (가능) 횟수: 13개

저의 이론에 따르면 k=6이고 6과 6사이 간격은 6, 이 숫자는 k+1=7보다 작으므로
2(k+1)-1 = 2 *7 -1 =13개


3) 0 ~ 49의 경우

0 (+1) 1 (+2) 3 ⋯ (+6) 21 (+7) 28 (+6) 34 (+5) 39 (+4) 43 (+3) 46 (+2) 48 (+1) 49 (가능) 횟수: 13개

저의 이론에 따르면 k=6이고 6과 6사이 간격은 7, 이 숫자는 k+1=7과 같으므로
2(k+1)-1 = 2 *7 -1 =13개

4) 0 ~ 50의 경우

0 (+1) 1 (+2) 3 ⋯ (+6) 21 (+8) 29 (+6) 35 (+5) 40  ⋯ (+1) 50 (불가능) 횟수: 13개
0 (+1) 1 (+2) 3 ⋯ (+5) 15 (+6) 21 (+5) 26 (+4) 30 (+5) 35 (+5) 40  ⋯ (+1) 50 (가능) 횟수: 14개

저의 이론에 따르면 k=6이고 6과 6사이 간격은 8, 이 숫자는 k+1=7보다 크므로
2(k+1) = 2 *7  =14개
<그 과정으로 분배되는 숫자는 알아서 잘 분배됨>

ALL RIGHT RESERVED TWINSTARINFO