You Nicholas

가고 가고 또 가면 알게되고, 행하고 행하고 또 행하게 되면 이루게 된다.

1 분 소요

1. 문제Permalink

[Bronze III] 분산처리 - 1009Permalink

문제 링크

성능 요약Permalink

메모리: 30860 KB, 시간: 120 ms

분류Permalink

구현(implementation), 수학(math)

문제 설명Permalink

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

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

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

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

입력Permalink

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

출력Permalink

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

출처: 백준, https://https://www.acmicpc.net/

2. 해결방법 시간복잡도Permalink

  1. 단순 코딩 O(N)

3. 문제 해결 및 코드Permalink

T = int(input()) # T만큼의 개수
for i in range(T):
a, b = map(int, input().split())
a = a % 10 # 들어오는 값을 한자리 숫자로 변환
if a == 0: # a가 0이면, 10으로 나눠지기때문에
print(10) # 10의 배수 컴퓨터
elif a == 1 or a == 5 or a == 6: #10으로 나누고 남은 값이 1 5 6, 1의 자리가 하나뿐이기 때문에
print(a) # a값 출력
elif a == 4 or a == 9: # 4, 9 는 2개이므로
b = b % 2 # 2로 나눠주고
if b == 1: # 1이 남는 수 == 9이므로 9 출력
print(a)
else:
print((a * a) % 10) # 아니라면 6 출력
else: # 남은 값인 2, 3, 7, 8
b = b % 4 # 남은 값들은 1자리수가 4개로 돌아가기때문에 4로 나눠주고
if b == 0: # 만약 해당 값이 0이라면
print((a ** 4) % 10) # 지수가 4의 배수와 같다. 이후에 10으로 나눠준다.
else: # 0이 아니라면
print((a ** b) % 10) # 아니라면 승수만큼 제곱해준다. 이후에 10으로 나눠준다.
view raw 1009.py hosted with ❤ by GitHub

  • 주석을 참고하면서 이해를 돕습니다.Permalink

4. 알고리즘 및 해설Permalink

  1. 받아야할 값은 T 만큼 받는다.
  2. 반복문이 T만큼 돌아가는 동안 a, b라는 값을 계속해서 받고 a를 10으로 나눠 한자리 숫자로 변환한다.
  3. 이때 변환된 값의 나머지를 if문을 통해 몇 가지의 경우수로 나눈뒤 값을 받는다.

5. 짚고 넘어가기Permalink

import sys
input = sys.stdin.readline
T = int(input())
for _ in range(T):
a,b = map(int,input().split())
aa=a%10
if aa == 0:
print(10)
elif aa in [1,5,6]: print(aa) # 1, 5, 6이 남는 값이 되는 경우
elif aa in [4,9]: # 4, 9가 남는 경우
bb=b%2 # 2가지 경우의 수이므로
if bb == 0: print(aa*aa%10)
else:
print(aa)
else: # 위의 숫자를 제외한 남는 값 2, 3, 7, 8
bb=b%4
if bb ==0: print(aa**4%10) # 지수가 4의 배수와 같으므로
else: print(aa**bb%10) # 승수만큼의 제곱
view raw 1009_2.py hosted with ❤ by GitHub
  1. 해당 방식으로 sys.stdin.readline을 통해 값을 전달받은 경우 메모리 효율을 높일 수 있다.
  2. 위의 코드와 거의 유사하지만 백준의 통과시간의 경우 64ms로 거의 2배가량 빠른 것을 볼 수 있다.

참고