[python] 백준 1009 : 분산처리

1번데이터 -> 1번컴퓨터 ... 10번데이터 -> 10번컴퓨터, 11번데이터 -> 1번컴퓨터 ... 

그렇다면 1091번데이터는 -> 1번컴퓨터입니다. 10번단위로 순환되므로 컴퓨터번호는 데이터의 일의자리수로 판단할수있습니다. 

 

문제를 해결하기위해선

＊a^b를 계산해 문자열로 만든후 가장 끝자리수를 출력하는방식이 있을것이고

＊어떤 정수를 제곱했을때 일의자리수는 순환되므로 순환규칙을 이용할수도 있을겁니다.

 

첫번째 방법은 느낌상 안될거같죠? 이전에도 시간초과의 경험이 있기때문에 계산이 길어지는것에 대해 경계해야합니다.

T=int(input())

for _ in range(T):
    a,b=map(int,input().split())
    n=str(a**b)

    print(n[len(n)-1])

첫번째방법을 구현한 코드입니다. 이렇게 끝낸다면 좋겠으나... a의 최댓값이 100, b의 최댓값이 100만인데 그냥 제곱해버리면 계산시간이 상당할겁니다. for문은 그냥 입력받은 T에대해서만 반복하기에 for문으로 인한 시간복잡도 증가는 시간초과에 영향을 크게 미치지않을겁니다. 그냥 어마무시하게 큰 스케일의 숫자계산이 문제죠

 

네 역시 안되네요. 빨리접고 두번째 방법을 생각해봅시다. 먼저 규칙에대해 알아봅시다

표는 0~9까지 숫자를 1~4제곱했을때 나오는 숫자의 일의자리수를 기록한것입니다. 0,1,5,6은 아예 일의자리수가 고정이고 2,3,7,8은 4제곱을 주기로 순환, 4,9는 2제곱을 주기로 순환합니다.

그럼 이 규칙을 알고리즘에 어떻게 써야할까요? 표를 만들면서 벌써 답을 얻어버렸습니다. a^b의 일의자리수를 파악하기위해 필요한것은 a가 표의 0~9중 어디에 해당하는지, b가 1~4제곱중 어디에 해당하는지를 파악하면 됩니다.

 

즉, a^b의 일의자리수를 파악하려면 a의 일의자리수와 b의 4순환 주기에서 위치만 알면된다는겁니다. b의 4순환주기에서 위치는 b를 4로 나눈 나머지로 알수있습니다. b를 4로 나눈 나머지가 0이라면 (b가 4의 배수라면) b는 표의 '4제곱'에 위치합니다. 만약 나머지가 1이라면 1제곱, 2라면 2제곱이겠죠.

 

T=int(input())

for _ in range(T):
    a,b=map(str,input().split())
    result=0
    
    a_0=int(a[len(a)-1])
    b_0=int(b)%4

    if b_0!=0:
        result=int(str(a_0**b_0)[len(str(a_0**b_0))-1])

    elif a_0==0:
        result=10

    else:
        result=int(str(a_0**4)[len(str(a_0**4))-1])

    print(result)

위의 계산을 구현한 코드입니다. a_0은 a의 일의자리, b_0은 b를 4로나눈 나머지(순환주기)입니다. a와 b를 문자열로 받아 일의자리 계산을 원활히 할수있습니다. 근데.. 틀렸네요. 

코드가 입력예시에 대해선 다 맞는 값을 출력하지만 틀린경우엔.. 반례를 파악해야하는데 참 어려워지죠.

고장난 부분을 파악해야하니 특이값 기준으로 일단 입력을 계속 해봅시다.

 

예제출력에 없는값들을 유도하기위해 입력값을 넣다보면 앗 특이점 발견! a_0==0일때 (a가 10의 배수일때) 이땐 a^b의 일의자리가 0이므로 10번째 컴퓨터를 사용해 10을 출력해야하는데 0이 출력됩니다. elif로 해당조건을 넣어줬으나... 작동이 안하는건가요?

 

원인을 유추해보면 첫번째 if는 b_0에 대한 조건만있고 elif는 a_0에 대한 조건입니다. a_0과 b_0은 서로 독립적입니다. 즉, b_0에 대한 조건은 a_0에 대한 컨트롤을 함에 있어서 아무런 권한이 없다는거죠.

 

예를들어 입력값이 a=20, b=721라고 해봅시다. 이 값은 첫번째조건인 b_0!=0을 충족하므로 첫번째 if문이 실행됩니다. 첫번째 if문에 의해 result=0이되고, 첫번째 if문이 실행됐으므로 아래 elif문은 실행되지않습니다. 그대로 0이 출력되죠

만약 b가 4의 배수인경우(b_0==0인경우), 예를들어 a=30, b=724인경우에는 elif가 실행되면서 (elif또한 b에대한 조건은없고 a에 대한 조건뿐이지만 if문 조건에 안걸리고 elif문 조건에 걸리므로 실행됩니다.) 10이 정상적으로 출력될겁니다..

 

입력값을 넣어보면 저의 추리가 맞았음을 알수있읍니다.. 이렇게 의심되는 부분에대한 test값을 만들어 직접 입력해보는것도 좋은 방법인거같습니다. 이제 if문에 살을붙여 코드를 다시 작성해줍시다.

 

T=int(input())

for _ in range(T):
    a,b=map(str,input().split())
    result=0
    
    a_0=int(a[len(a)-1])
    b_0=int(b)%4

    if b_0!=0 and a_0!=0:
        result=int(str(a_0**b_0)[len(str(a_0**b_0))-1])

    elif a_0==0:
        result=10

    else:
        result=int(str(a_0**4)[len(str(a_0**4))-1])

    print(result)

 

if문의 head 조건부를 자세히 적지않아 발생한 문제였습니다. 변수가 2개라면 각각에 대한 조건을 설정해 독립적으로 and던 or이던 이용해서 각각 기술해줘야합니다.