[구현] 백준 1009번 분산처리 Python 풀이

문제 요약

1부터 10까지 번호를 부여한 컴퓨터가 특정 패턴에 따라 데이터를 처리한다.

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

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

총 데이터의 개수는 항상 a의 b제곱 형태로 주어진다.

마지막 데이터가 처리될 컴퓨터의 번호를 찾는 프로그램을 작성하라.

백준 1009번 문제 바로가기

입력

첫 번째 줄에 테스트 케이스 개수 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

코드

정답 예시 1

약 1시간 10분 소요

N = int(input())
# a의 b 제곱값의 1의 자리 수의 패턴 저장
array = [[0], [1], [2, 4, 8, 6], [3, 9, 7, 1], [4, 6, 4, 6], [5], [6], [7, 9, 3, 1], [8, 4, 2, 6], [9, 1, 9, 1]]

for _ in range(N):
    # a, b값 입력 받음
    a, b = map(int, input().split())
    # a가 10의 배수일 경우, 10 출력
    if a % 10 == 0:
        print(10)
        continue
    # a % 10이 1, 5, 6일 경우, a % 10 값 출력
    elif a % 10 == 1 or a % 10 == 5 or a % 10 == 6:
        print(a % 10)
        continue
    # b가 0이면 1 출력
    if b == 0:
        print(1)
    # b % 4가 0이면, array에 저장해둔 패턴값 가져옴
    elif b % 4 == 0:
        print(array[a % 10][3])
    else:
        print(array[a % 10][b % 4 - 1])

 

한 줄 입력받고 바로 출력

정답 예시 2

약 1시간 10분 소요

T = int(input())
value = [[0] * 2 for _ in range(T)]
for i in range(T):
    value[i][0], value[i][1] = map(int, input().split())
array = [[0], [1], [2, 4, 8, 6], [3, 9, 7, 1], [4, 6, 4, 6], [5], [6], [7, 9, 3, 1], [8, 4, 2, 6], [9, 1, 9, 1]]

for i in range(T):
    a = value[i][0]
    b = value[i][1]
    if a % 10 == 0:
        print(10)
        continue
    elif a % 10 == 1 or a % 10 == 5 or a % 10 == 6:
        print(a % 10)
        continue
    if b == 0:
        print(1)
    elif b % 4 == 0:
        print(array[a % 10][3])
    else:
        print(array[a % 10][b % 4 - 1])

모든 입력값을 저장한 뒤, 꺼내서 계산

피드백

예전에 풀려고 시도했던 문제였는데, 시간 초과로 포기했었다.

이번에 다시 풀어보려고 했더니 패턴을 비교적 빠르게 찾을 수 있었다.

구현해내는데는 시간이 좀 걸렸지만, 문제를 제대로 읽고 변수를 예상했다면 더 빠르게 해결할 수 있었을 것이다.

 

내가 찾은 패턴

• 데이터 번호 % 10의 값이 1, 5, 6일 경우 그대로 출력, 10일 경우 0 출력
• b가 0일 경우, 1 출력
• 그 외일 경우(2, 3, 4, 7, 8, 9) 패턴 존재. 해당 패턴을 저장해두고 접근하면 시간 초과에 걸리지 않는다.

다른 사람 풀이 참고

- 다른 사람 풀이법 참고 후 수정 예정

깨달은 것

• 입력받는 것, list 초기화하는 것이 부족
• 문제를 제대로 읽지 않아서 놓치는 부분이 있음
  (여기서는 a % 10 == 0에 대한 처리, b가 0일 때 처리)