백준 1009 분산처리 만만치않은 브론즈2

문제설명

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

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

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

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

 

=> 즉 a**b를 10으로 나눈  나머지를 구하는 문제

 

입력

1. 테스트케이스의 개수 T

2. a,b

5
1 6
3 7
6 2
7 100
9 635

 

 

출력

데이터가 마지막으로 처리되는 컴퓨터의 번호 

1
7
6
1
9

 

---

 

 

풀이

1차 시도

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

for _ in range(N) :
  a,b = map(int,sys.stdin.readline().strip().split())
  
  print(a**b%10)

• 너무 쉬운 문제인데? 역시 브론즈다~ 하고 신나게 썼지만
• 시간초과

 

• 정답률 낮은데에는 이유가 있었다...

 

 

 

 

2차 시도

import sys

N = int(sys.stdin.readline().strip())
 
def pow(a,b) :
  if b <= 1 :
    return a
  n = pow(a,b//2)

  # 짝수
  if b % 2 == 0 :
    return n * n
  # 홀수
  else :
    return n*n*a


for _ in range(N) :
  x,y = map(int,sys.stdin.readline().strip().split())

  
  ans = pow(x,y)
  print(ans%10)

• 재귀로 풀기!
• 오랜만이라 생각해내는데 한참 걸렸다
• 하지만 시간초과

 

???

 

 

 

3차 시도 : 정답

import sys

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


for _ in range(N) :
  x,y = map(int,sys.stdin.readline().strip().split())

  x = x%10
  if x == 0 :
    print(10)
    continue


  cycle = []
  temp = x
  while temp not in cycle :
    cycle.append(temp)
    temp = (temp * x) % 10

  
  idx = (y-1) % len(cycle)
  print(cycle[idx])

 

• 제곱 % 10의 규칙을 활용하여 푸는 문제

 

  x = x%10
  if x == 0 :
    print(10)
    continue

 

• 가지치기 : 나머지가 0이면 10번째니까 더 계산하지 않고 10을 출력해서 시간을 절약함

  cycle = []
  temp = x
  while temp not in cycle :
    cycle.append(temp)
    temp = (temp * x) % 10

 

• cycle 에 나머지로 나오는 규칙적인 값을 저장함
• while문을 통해 사이클을 한 바퀴 돌림
  • 이때 x(고정적인 값)가 아닌 temp(변하는 값)로 적어야 함!

 

  idx = (y-1) % len(cycle)
  print(cycle[idx])

• cycle에서 원하는 인덱스 찾기
• 인덱스는 0부터 시작하는데 지수는 1부터 시작하므로 y-1 해줌
  • ` y%len(cycle) -1`을 하면 안되는 이유 :
    • y%len(cycle)의 값이 0이 나왔을 때 음수 인덱스가 나와 오류가 생길 수 있음
    • 파이썬은 -1을 하면 뒤에서 1번째를 가져오니까 괜찮긴하지만..! 다른 언어에서는 음수인덱스는 오류를 발생시킴