[백준/파이썬] 1009번: 분산처리

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

1009번: 분산처리

문제 풀이 과정

이 문제를 풀어본 결과, 나는 개 빡대가리가 분명하다. 좀만 침착하게 생각해봐도 여러번 틀리지 않아도 됐을 간단한 문제인데, 조건에 대한 범위를 설정하는 데에 있어서 자꾸 빵꾸가 나서 에러가 여러번 발생하게 되었다. 

T = int(input())
answers = []

for i in range(T):
    a, b = map(int, input().split())
    answers.append(a ** b % 10)

for i in answers:
	print(i)

위의 간단한 방식대로 풀어도 원하는 결과값들은 나올 수 있겠으나, b의 범위가 1 ≤ b < 1,000,000으로, 무려 백만까지 가기 때문에 그만큼 제곱하게 되면 시간이 어마어마하게 많이 소요되어서 시간 초과가 발생한다. (나도 당연히 아무생각없이 위의 코드대로 해서 제출했다가 시간 초과를 경험했다..) 

 

따라서, 이 문제와 같은 경우는 각 숫자들(a)을 제곱할 때에 있어서 제일 뒷자리 수가 몇 번째 돌 때 반복되게 되는지를 각각 파악하는 것이 중요하다. 따라서, 이 문제 자체를 풀기 전, 맨 뒷자리가 0부터 9까지인 각각의 수들은 몇 번째 순서로 제곱할 때 다시 기존의 수로 돌아오게 되는지를 파악하도록 했다.

pattern = {0:0}

init = -1
for i in range(1, 10) :
  for j in range(1, 11) :
    if (j == 1) :
      init = i
    else :
      num = i ** j
      if (init == (num % 10)):
        pattern.update({init : j-1})
        break

# {1: 1, 2: 4, 3: 4, 4: 2, 5: 1, 6: 1, 7: 4, 8: 4, 9: 2}

이제 이렇게 맨 끝자리수들의 규칙을 알아내었다면, 그 규칙을 사용해서 큰 숫자들로 제곱하는 경우들을 보다 작은 숫자들로 제곱하도록 변경해주는 작업을 수행해야 한다. 그러나, 나의 경우는 이 과정에서 자꾸만 빠뜨리는 반례들이 많았어서 여러번 틀리고 시간도 오래 걸렸던 것 같다. 여기서 주의해야 할 점은 맨 끝자리가 0일 때는 그냥 무조건 10이 출력되어야 한다는 점이고, 2나 4의 주기로 반복되는 수일 경우에는 나머지가 0이 나오는 경우와 그렇지 않은 경우를 잘 구분해서 코드를 작성해야 한다.

(반례: a가 4이고, b도 4인 경우 등..)

 

이 문제의 핵심은 빠뜨리는 사례들 없이 조건을 잘 설정하는 것이라고 개인적으로 생각을 하기 때문에 조건 범위 설정을 잘만 한다면 큰 문제 없이 이 문제를 해결할 수 있으리라 생각된다.

정답 예시 코드 (Python)

T = int(input())

pattern = {0:0}

init = -1
for i in range(1, 10) :
  for j in range(1, 11) :
    if (j == 1) :
      init = i
    else :
      num = i ** j
      if (init == (num % 10)):
        pattern.update({init : j-1})
        break

# {1: 1, 2: 4, 3: 4, 4: 2, 5: 1, 6: 1, 7: 4, 8: 4, 9: 2}

answers = []
for i in range(T) :
  a, b = map(int, input().split())
  dupl = pattern[a % 10]
  if (dupl == 0) :
    answers.append(10)
    continue
  if (dupl == 1) :
    b = 1
  elif (dupl == 2) :
    b = b % 2
    if (b == 0) :
      b = 2
  elif (dupl == 4) :
    b = b % 4
    if (b == 0) :
      b = 4
  answers.append(a ** b % 10)

for i in answers:
  print(i)