[백준 19940] 2020 정올 1차 초등부 "피자 오븐"(1)

문제 출처 : https://www.acmicpc.net/problem/19940

19940번: 피자 오븐

이 문제는 2020년 정보 올림피아드 초등부 2번 문제 입니다.

문제 이해하기

버튼을 어떻게 누르는 것이 더 적은 횟수로 누를 수 있는지 찾는 문제 입니다. 이런 문제는 직접 계산을 하던가, 알고리즘을 통해 최소 버튼 횟수를 찾는 방법이 있습니다.

BFS를 사용하면 버튼의 최소 횟수를 찾을 수 있지만 여기서는 직접 계산하는 방법을 생각해 보겠습니다.

6분 이상일 때

먼저 가장 먼저 생각할 수 있는 것인 6분 이상일 때 입니다. 5분까지는 1분 버튼을 5번 누르는 것이 최소 이지만 6분 부터는 1분 버튼 6번 보다, 10분 버튼 1번에 -1분 버튼 4번을 누르는 것이 5번으로 최소가 됩니다.

40분 이상일 때

다음으로 40분 이상일 때 10분 버튼 4번 보다, 1시간 버튼 1번에 -10분 버튼 2번이 최소 횟수 3번이 됩니다.

45, 55분 일 때

다음으로 위에 걸리지 않지만 45분 55분일 경우 횟수를 줄일 수 있습니다. 45분을 예로 들면 첫 번째로는 10분 버튼 4번, 1분 버튼 5번으로 총 9번을 눌러야 합니다. 두 번째로 위에서 언급한 40분에 걸리기 때문에 횟수를 줄일 수 있습니다. 60분 버튼 1번, -10분 버튼 2번, 1분 버튼 5번으로 8번에 가능 합니다.

세 번째로 60분 버튼 1번, -10분 버튼 1번, -1분 버튼 5번으로 7번안에 가능해 집니다. 5분을 누를 때 1분을 5번 누르는 것이, 10분 1번 -1분 5번 누르는 것보다 횟수가 적어지지만 45분, 55분일 때에는 -10분 버튼을 한 번 덜 누르고 -1분 버튼을 누르는 것이 더 효율적으로 되는 것입니다.

코드 작성하기

코드를 작성해 보겠습니다.

입력 받기

T = int(input())

for _ in range(T):
    n = int(input())
    solve(n)

테스트 케이스 T개를 입력 받습니다. 다음으로 설정해야 하는 시간 n을 입력 받습니다. solve라는 함수를 사용하여 결과를 출력하도록 하였습니다.

solve 함수

def solve(n):
    ah = at = mt = ao = mo = 0
    ah = n // 60
    n %= 60

    at = n // 10
    n %= 10

    ao = n

    if 4 <= at and ao == 5:
        ah += 1
        at -= 5
        ao = -5

    if 6 <= ao:
        at += 1
        ao -= 10

    if 4 <= at:
        ah += 1
        at -= 6

    if at < 0:
        mt = -at
        at = 0
        
    if ao < 0:
        mo = -ao
        ao = 0

    print(ah, at, mt, ao, mo)

solve 함수에는 먼저 1시간을 더하는 ah, 10분을 더하는 at, 10분을 빼는 mt, 1분을 더하는 ao, 1분을 빼는 mo를 0으로 세팅 합니다.

시간 버튼 ah는 무조건 누르는 것이 좋습니다. 따라서 n을 60으로 나눈 값을 가집니다. 그리고 n은 60으로 나눈 나머지를 가지게 됩니다.

다음으로 10분 버튼을 누르는 횟수로 변경하기 위해 10으로 나눈 값이 at가 됩니다. 그리고 남은 값은 1분을 누른 횟수인 ao가 됩니다.

이제 바꿀 수 있는 값을 바꿔 줍니다. 위에서 언급했던 45분 55분부터 수정 합니다. at가 4보다 크고, ao가 5인 경우가 45분, 55분 입니다. 이럴 경우는 한시간 버튼 ah를 누르고 at값은 5를 빼줍니다. ao는 5이기 때문에 그냥 -5로 바꿔 줍니다. at, ao에 음수가 있지만 뒤에서 한꺼번에 바꿔줄 예정 입니다. 여기서 -10분, -1분 버튼 조절을 할 수도 있지만 버튼 하나하나 신경쓰는 것이 더 어렵게 느껴질 수 있습니다.

다음으로 6분 이상일 경우에는 at 버튼 1번 눌러 10분을 늘려주고, ao는 10번을 빼줍니다. 40분 이상일 경우에도 ah 버튼 1번 눌러 60분 늘려주고, 10분 버튼인 at를 6번을 빼줍니다.

마지막으로 10분 버튼이 음수라면 이 값을 mt로 변경하고, 1분 버튼 ao가 음수라면 mo 버튼 값으로 변경해 줍니다. 모든 버튼 값이 완성 되었으면 그 값을 출력해 주면 됩니다.

전체 코드

전체 코드를 확인해 보겠습니다.

T = int(input())

def solve(n):
    ah = at = mt = ao = mo = 0
    ah = n // 60
    n %= 60

    at = n // 10
    n %= 10

    ao = n

    if 4 <= at and ao == 5:
        ah += 1
        at -= 5
        ao = -5

    if 6 <= ao:
        at += 1
        ao -= 10

    if 4 <= at:
        ah += 1
        at -= 6

    if at < 0:
        mt = -at
        at = 0
        
    if ao < 0:
        mo = -ao
        ao = 0

    print(ah, at, mt, ao, mo)

for _ in range(T):
    n = int(input())
    solve(n) 

 

BFS로 푸는 방법은 다음 포스팅에 올리도록 하겠습니다.