백준/1009번 :: 분산처리 (Python, 파이썬, 알고리즘)

 

문제

---

 

재용이는 최신 컴퓨터 10대를 가지고 있다. 어느 날 재용이는 많은 데이터를 처리해야 될 일이 생겨서 각 컴퓨터에 1번부터 10번까지의 번호를 부여하고, 10대의 컴퓨터가 다음과 같은 방법으로 데이터들을 처리하기로 하였다.

1번 데이터는 1번 컴퓨터, 2번 데이터는 2번 컴퓨터, 3번 데이터는 3번 컴퓨터, ... ,

10번 데이터는 10번 컴퓨터, 11번 데이터는 1번 컴퓨터, 12번 데이터는 2번 컴퓨터, ...

총 데이터의 개수는 항상 ab개의 형태로 주어진다. 재용이는 문득 마지막 데이터가 처리될 컴퓨터의 번호가 궁금해졌다. 이를 수행해주는 프로그램을 작성하라.

입력

---

 

입력의 첫 줄에는 테스트 케이스의 개수 T가 주어진다. 그 다음 줄부터 각각의 테스트 케이스에 대해 정수 a와 b가 주어진다. (1 ≤ a < 100, 1 ≤ b < 1,000,000)

 

출력

---

 

각 테스트 케이스에 대해 마지막 데이터가 처리되는 컴퓨터의 번호를 출력한다.

 

예제

---

 

예제입력

5
1 6
3 7
6 2
7 100
9 635

 

예제출력

1
7
6
1
9

 

코드

---

 

# -*- coding: utf-8 -*-
# Python 3.4.5
import sys
t = int(sys.stdin.readline())
for _ in range(t) :
    # 입력
    a, b = map(int, sys.stdin.readline().split())
    
    # 불필요한 연산 제거
    if a == 1:
        print(1)
        continue
    elif a == 5:
        print(5)
        continue
    elif a == 6:
        print(6)
        continue

    # 계산
    result_list = []    # 반복되는 숫자 리스트
    temp = 1
    for _ in range(b):
        temp *= a
        temp %= 10
        if temp in result_list:
            break
        result_list.append(temp)
    
    # 결과 출력
    result = result_list[b%len(result_list)-1]
    if result == 0:
        print(10)
    else:
        print(result)
​

 

전체 숫자를 계속 곱해나가면 시간초과가 발생한다. 쓸데없이 연산을 많이 하게된다. 살펴보면 1의자리만 가지고 풀수있다.

 

그리고 숫자가 반복되는 것을 확인 할 수 있다. 예를들어, 3의 경우

3 9 7 1 3 9 7 1 3 9 7 1 3 9 7 1 ...(생략)...

위와같이 3, 9, 7, 1이 반복된다.

 

만약 16번째 숫자가 궁금한 경우, 인덱스 0번째부터 시작했을때, (16%4)-1 번째 값을 가져오면 된다.

 

크게 차이는 없지만 시간을 더 줄이고 싶다면, 1과 5, 6의 숫자는 아무리 곱해도 항상 같은 값이 나온다. 이런경우 뒤에 연산을 할 필요없이 바로 결과를 반환하면 된다. (코드 9번줄~18번줄)

 

결과

---

 

 

※ 직접 문제 풀고 돌려본 뒤, 채점까지 마친 후에 작성한 글입니다.

더 좋은 방법이 있다면, 댓글로 알려주시면 감사하겠습니다 :)

 

문제 출처

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