추석맞이 코딩 문제 챌린지 LV.2 정상 정복

 

[추석맞이 코딩챌린지②] 정상 정복

 

문제

달팽이는 높이가 N인 나무를 올라가고자 한다.

달팽이는 낮에는 A미터를 올라갈 수 있지만, 밤에 휴식을 취하면서 B미터 미끄러져 내려온다.

 

달팽이가 나무 정상에 도달하기 위해선 며칠이 걸릴까요?

 

조건

• 첫 번째 줄에 A, B, N이 공백으로 구분되어 주어집니다.
• 정상에 도달하는 게 불가능할 경우, -1을 출력하세요.

 

입출력 예시

예제 입력 1

2 1 5

예제 출력 1

4

 

예제 입력 2

100 101 1000000000

예제 출력 2

-1

 

---

힌트

반복문 중 while문을 사용하여 풀 수 있다.

종료 조건을 잘 생각해서 풀어보자

---

정답 코드

- C언어

#include <stdio.h>

int main(){
    int A, B, N, height = 0, day = 0;

    // 달팽이는 높이가 N미터인 나무를 올라가고자 한다.
    // 낮에는 A미터를 올라가고 밤에는 B미터를 미끄러져 내려온다.
    // height 변수에 현재 달팽이가 얼마나 높이 올라갔는지 저장한다.
    // day 변수에 며칠이 걸리는지 저장한다.
    scanf("%d %d %d", &A, &B, &N);

    while(1){
        if(height < 0){     // 현재 높이가 음수 높이가 된다면
            day = -1;       // 올라가는 높이보다 미끄러져 내려오는 높이가 더 크다는 것이므로
            break;          // day에 -1을 저장하고 반복문을 종료한다.
        }

        day ++;             // 하루가 시작한다
        height += A;        // 낮에는 A만큼 올라가고

        if(height >= N) break;    // 이때 N미터인 나무의 정상까지 올라갈 수 있으면 반복문을 종료한다.
        
        height -= B;        // 밤에는 B만큼 내려온다
        
    }

    printf("%d", day);

    return 0;
}

- Python

# 달팽이는 높이가 N미터인 나무를 올라가고자 한다.
# 낮에는 A미터를 올라가고 밤에는 B미터를 미끄러져 내려온다.
# height 변수에 현재 달팽이가 얼마나 높이 올라갔는지 저장한다.
# day 변수에 며칠이 걸리는지 저장한다.
A, B, N = map(int, input().split())
height, day = 0, 0

while True:
    if height < 0:      # 현재 높이가 음수 높이가 된다면
        print(-1)       # 올라가는 높이보다 미끄러져 내려오는 높이가 더 크다는 것이므로
        break           # day에 -1을 저장하고 반복문을 종료한다.

    day += 1            # 하루가 시작한다
    height += A         # 낮에는 A만큼 올라가고

    if height >= N:     # 이때 N미터인 나무의 정상까지 올라갈 수 있으면 반복문을 종료한다.
        print(day)
        break

    height -= B         # 밤에는 B만큼 내려온다

 

---

풀이

종료 조건을 잘 설정하지 못해서 실수할 수 있는 문제다.

코드에서 주석으로 설명해뒀지만 결과를 도출하기 위해 A, B, N을 제외한 두 개의 변수가 더 필요하다.

지금까지 달팽이가 얼마나 높이 올라갔는지에 대한 변수와 지금까지 며칠이 지났는지에 대한 변수이다.

 

반복문을 통해 달팽이의 현재 높이를 계산할 수 있으며 이때 달팽이가 며칠 만에 정상에 도달할지 모르기 때문에 for 반복문보다는 while 반복문이 더 적합하다.

 

현재 높이인 height에서 낮에 A만큼 올라감으로써 나무를 오를 수 있으면 다시 내려올 필요 없이 바로 종료시키면 된다.

 

---

심화

수학

이 문제를 반복문으로 풀 수도 있지만 만약 N이 100억이고 A가 2, B가 1일 경우를 생각해보자. 이걸 반복문으로 결과를 도출해낸다면 한세월이 걸릴 것이다. 이럴 경우에 수학적인 공식 하나로 0.01초 만에 결과를 도출해낼 수 있다.

 

아래 그림을 보자.

 

 

오르고자하는 나무의 높이는 N 미터이고 달팽이가 하루에 오를 수 있는 최대 A 미터이다. 상식적으로 생각해보면 달팽이가 마지막 날에 A 미터를 올라가면서 N미터에 도달하지 B미터를 떨어지면서 N미터에 도달하지는 않을 것이다.

따라서 전체 나무의 높이인 N 미터에서 마지막 날에 오르는 A 미터를 빼고 생각해보자. 그럼 나머지 N - A 미터를 오를 때는 낮에 A미터가 오르고 밤에는 B미터를 내려오기 때문에 하루에 달팽이가 오르는 높이는 A - B미터가 될 것이다. 즉, 달팽이가 N미터를 오르기 위해서는 N - A미터를 A - B미터로 며칠 만에 오를 수 있는지 수학적으로 계산한 후 1을 더한 만큼의 시간이 필요한 것이다.

 

- C언어

#include <stdio.h>

int main(){
    int A, B, N, day;

    // 달팽이는 높이가 N미터인 나무를 올라가고자 한다.
    // 낮에는 A미터를 올라가고 밤에는 B미터를 미끄러져 내려온다.
    scanf("%d %d %d", &A, &B, &N);

    if(A <= B){
        printf("-1");
    }
    else{
        N -= A;         // N에서 A미터를 빼고 고려한다.
        day = N / (A - B);      // N - A를 하루에 오를 수 있는 높이 A - B를 나눈다

        if(N % (A - B)){    // A - B로 나눈 나머지가 남아있다면
            day ++;         // 남은 높이도 올라야하기 때문에 1을 더해준다.
        }

        printf("%d", day + 1);      // 마지막 날에 A만큼 오르기 때문에 A만큼 더해준다.
    }

    return 0;
}

 

- Python

# 달팽이는 높이가 N미터인 나무를 올라가고자 한다.
# 낮에는 A미터를 올라가고 밤에는 B미터를 미끄러져 내려온다.
A, B, N = map(int, input().split())

if A <= B:      # A가 B보다 같거나 작다면 N미터에 도달할 수 없기 때문에 -1을 출력한다.
    print(-1)

else:
    N -= A      # N에서 A미터를 빼고 고려한다.
    day = N // (A - B)      # N - A를 하루에 오를 수 있는 높이 A - B를 나눈다

    if N % (A - B):         # A - B로 나눈 나머지가 남아있다면
        day += 1            # 남은 높이도 올라야하기 때문에 1을 더해준다.
    
    print(day + 1)          # 마지막 날에 A만큼 오르기 때문에 A만큼 더해준다.