[백준] 31416번 가상 검증 기술

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

31416번: 가상 검증 기술

풀이

입력의 테스트 케이스가 총 1000, 테스트의 갯수가 100, 최대 시간이 100이기 때문에
최대 100 * 100 * 1000의 시간으로 풀더라도 1억보다 작기 때문에 1초 안에 해결이 가능하다.

즉, 단순 구현으로도 수학적인 방법으로도 풀이가 가능한 문제이다.

먼저 단순 구현으로 풀어보겠다.
단순 구현으로 풀기 위해 실제 시간이 1씩 증가하는 방식을 사용하여 구현했다.
while 문을 돌리면서 시간이 1씩 증가하고 해당 시간에 업무가 완료되는지 새로 시작되는지 판단하는 방식이다.
이렇게 문제를 푸는 경우 시간이 너무 높거나 각 문제 사이의 텀(수행 시간)이 긴 경우에는 비효율적이다.

 가장 먼저 필요한 변수들이다. 
도훈이와 상혁이의 현재 상태를 나타내는 값이다. (일을 하고 있지 않음, A 일을 하고 있음, B 일을 하고 있음)

#일을 안하는 경우 -1, A를 하는 경우 0, B를 하는 경우 1

DH = -1
SH = -1

 

다음은 도훈이가 현재 일을 수행한 뒤 소요된 시간이다. 이 시간이 해당 업무를 수행하는 시간만큼 흘러가면 종료된 것으로 판단

# 현재 시간, DH이 업무한 시간, SH이 업무한 시간
        time = 0
        DH_count = 0
        SH_count = 0

 

이제 위에 정의한 변수들을 활용하여 실제 가상 검증을 수행하는 것처럼 코드를 구현한다.

 

import sys

N = int(sys.stdin.readline())

data = []

for i in range(N):
    data.append(list(map(int, sys.stdin.readline().split())))

DH = -1
SH = -1

기본 입력 + DH, SH의 상태를 나타내는 변수 정의

 

for i in data:
    B_time = i[1] * i[3]
    if i[0] * i[2] <= B_time:
        print(B_time)

 

입력받은 data를 돌아가면서 테스트 케이스에 대한 시간을 구한다.

i[0] - A시간,  i[1] - B시간, i[2] - A갯수, i[3] - B갯수

B_time 즉, 도훈이만 수행할 수 있는 업무가 상혁이도 수행할 수 있는 A의 총 시간보다 긴 경우에는 도훈이의 업무가 끝나는 순간이
테스트가 종료되는 순간이기 때문에 해당 경우를 미리 처리했다.

 

    else :
        time = 0
        DH_count = 0
        SH_count = 0
        # 아래 시간 구현 부분
        while(True):
            if i[2] == 0 and i[3] == 0 and DH == -1 and SH == -1:
                break

위 조건을 만족하지 않는 경우는 시간이 0에서부터 증가하면서 실제로 시뮬레이션을 하였다.
초기에 도훈과 상혁의 업무 시간을 0으로 초기화한다.

이후 while문을 이용하여 구현하는데 먼저 초기 조건으로 남은 A, B의 업무의 갯수가 없고, 도훈과 상혁이 일을 안하고 있으면
종료된 것으로 설정했다.

 

            if DH == -1:
                if i[3] > 0:
                    i[3] -= 1
                    DH = 1
                    DH_count = 0
                elif i[2] > 0:
                    i[2] -= 1
                    DH = 0
                    DH_count = 0
            

            if SH == -1:
                if i[2] > 0:
                    i[2] -= 1
                    SH = 0
                    SH_count = 0

도훈이 일을 안하고 있으면(-1) 먼저 B는 도훈밖에 할 수 없기 때문에 먼저 시킨다.
B의 남은 일이 없다면 A의 일을 수행한다.

상혁은 항상 A의 일만 할 수 있기 때문에 A만 수행하게 한다.

도훈, 상혁 모두 일을 시작할 때 현재 업무가 진행된 시간은 0으로 초기화하고 현재 수행하고 있는 업무 A(0), B(1)을 상태로 표시한다.

 

            time += 1
            DH_count += 1
            if DH == 1 and DH_count == i[1]:
                DH_count = 0
                DH = -1
            elif DH == 0 and DH_count == i[0]:
                DH_count = 0
                DH = -1

            SH_count += 1
            if SH == 0 and SH_count == i[0]:
                SH_count = 0
                SH = -1

다음 시간을 증가시켜 DH_count +1을 한다.
이후 도훈이 하고 있는 일 A라면 A의 시간, B라면 B의 시간과 현재 DH_count의 시간이 일치하는지 확인하고
일치하면 해당 검증이 종료된 것으로 취급하여 도훈의 상태, 업무 시간을 초기화해준다.

동일하게 상혁도 구현했다. 할 수 있는 일이 A뿐이라 A에 대해서만 확인하면 된다.

 

시간 초과가 나왔다.
시간 복잡도 상으로는 문제 없을 것으로 생각되지만 파이썬의 수행 시간이 길어서 그럴 것으로 생각해 pypy3로 다시 확인했다.

 

정답은 나왔지만 앞서 말했던 것처럼 시간이 너무 길어지거나 검증의 시간이 긴 경우 효율성이 떨어진다.
더 효율적인 방법으로 풀 수 있을 것 같았다.

 

효율적인 방법
모든 경우의 수를 구해서 가장 짧은 시간이 나오게 문제를 구현하면 된다.
B검증은 모두 도훈이 수행, A검증에 대해서 도훈이 0개 수행할 때부터 N개(모두) 수행할 때까지 경우의 수 중 가장 낮은 값이 정답이다.

 

for i in data:
    answer = 100000

i[0] - A시간,  i[1] - B시간, i[2] - A갯수, i[3] - B갯수
먼저 초기 값을 설정한다. 최대 나올 수 있는 경우가 100 * 100이기 때문에 여유있게 10만으로 설정했다.

 

for j in range(i[2] + 1):
        temp = max(i[0] * j, i[0] * (i[2] - j) + i[1] * i[3])

        answer = min(answer, temp)
    
    print(answer)

그 후 j를 0부터 A의 갯수까지 반복하면서 
상혁이가 검증을 j 개 할 때, 도훈이가 B업무를 모두 끝내고 검증을 N - j 개 할 때 중 큰 값(검증이 모두 종료된 값)
들 중 가장 작은 값을 찾았다.

일을 나눠서할 수 있는 모든 경우의 수를 구하는 것이기 때문에 코드는 간결하고 빠르게 답을 얻을 수 있다.

 

 

 

전체 코드 1.

import sys

N = int(sys.stdin.readline())

data = []

for i in range(N):
    data.append(list(map(int, sys.stdin.readline().split())))

DH = -1
SH = -1

for i in data:
    B_time = i[1] * i[3]
    if i[0] * i[2] <= B_time:
        print(B_time)
    else :
        time = 0
        DH_count = 0
        SH_count = 0
        while(True):
            if i[2] == 0 and i[3] == 0 and DH == -1 and SH == -1:
                break

            if DH == -1:
                if i[3] > 0:
                    i[3] -= 1
                    DH = 1
                    DH_count = 0
                elif i[2] > 0:
                    i[2] -= 1
                    DH = 0
                    DH_count = 0
            

            if SH == -1:
                if i[2] > 0:
                    i[2] -= 1
                    SH = 0
                    SH_count = 0

            time += 1
            DH_count += 1
            if DH == 1 and DH_count == i[1]:
                DH_count = 0
                DH = -1
            elif DH == 0 and DH_count == i[0]:
                DH_count = 0
                DH = -1

            SH_count += 1
            if SH == 0 and SH_count == i[0]:
                SH_count = 0
                SH = -1


        print(time)

 

 

전체 코드 2.

N = int(input())

data = []

for i in range(N):
    data.append(list(map(int, input().split())))


for i in data:
    answer = 100000

    for j in range(i[2] + 1):
        temp = max(i[0] * j, i[0] * (i[2] - j) + i[1] * i[3])

        answer = min(answer, temp)
    
    print(answer)

아이디어에 따라서 단순하게도 복잡하게도 구현할 수 있는 문제였다.