[알고리즘 문제 풀이🙄] 20551. 증가하는 사탕 수열

📌 문제 요약

세 개의 상자가 나란히 있을 때 각 상자에 사탕을 A개, B개, C개 넣어두려 한다.

각 상자가 비어있지 않으면서 들어 있는 사탕의 개수가 순증가하도록 하려고 할 때, 이 조건을 맞추기 위해 넘치는 사탕을 세현이가 먹어 없앤다고 하면 최소 몇 개의 사탕을 먹어야 하는가?

(세 개의 자연수 A, B, C는 각각 1 이상 3000 이하의 값을 가진다.)

• 실행 시간: python 3초, java 2초

 

🤔 내가 생각한 로직

• A, B, C 순서로 사탕의 개수가 순증가해야 하므로, C부터 개수를 확인한다.
  • 다음으로 B는 C보다 최소 1 이상 적은 개수의 사탕을 가지도록 사탕을 먹어 없앤다.
  • 마지막으로 A는 B보다 최소 1 이상 적은 개수의 사탕을 가지도록 사탕을 먹어 없앤다.

 

😥 틀린 코드와 문제점

T = int(input())

for tc in range(1, T + 1):
    candies = list(map(int, input().split()))

    bf_cnt = candies[-1]
    toEat = 0

    for i in range(1, -1, -1):
        if candies[i] >= bf_cnt:
            toEat += candies[i] - bf_cnt + 1 
            candies[i] -= toEat
            bf_cnt = candies[i]
            if bf_cnt < 0:
                toEat = -1
                break
    
    print(f'#{tc} {toEat}')

 

▷시간 초과가 문제였던 것 같다. 

 

🤗 제출 후 pass한 코드

T = int(input())

for tc in range(1, T + 1):
    A, B, C = map(int, input().split())

    if C <= 2 or B <= 1:
        print(f'#{tc} -1')
        continue

    totalEat = toEat = 0

    if B >= C:
        toEat = B - C + 1
        B -= toEat
        totalEat += toEat
    
    if A >= B:
        toEat = A - B + 1
        A -= toEat
        totalEat += toEat

    print(f'#{tc} {totalEat}')

강사님 코드를 한번 훑어보고 작성한 코드이다.

 

🧐 참고할 코드

T = int(input())

for tc in range(1, T + 1):
    A, B, C = map(int, input().split())

    # A < B < C 구조로 만들 수 없는 케이스를 처리함
    if B < 2 or C < 3:
        print(f'#{tc} -1')
        continue

    eat = 0

    if B >= C:
        eat += B - (C - 1)
        B = C - 1

    if A >= B:
        eat += A - (B - 1)
        A = B - 1

    print(f'#{tc} {eat}')

 

😎 앞으로의 개선 방향

 

굳이 생성하지 않아도 될 변수나 리스트를 만들지 않도록 설계하는 연습을 해야겠다. 그리고 완전탐색을 하더라도 간단히 비교가 가능한 것은 굳이 반복문으로 구현하지 않아도 됨을 알게되었다.