[BAEKJOON_1009] 분산 처리(Python)

*출처

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

1009번: 분산처리

들어가기전 할말이 참 많은 문제...

브론즈3 풀다가, 처음으로 브론즈2 승급전을 치뤘다.. 결과는 참혹했다.

참혹한..

 역시 승급전은 코딩에서도 쉬운게 아님을 느끼며...

 오늘은 좀 길 예정이니... 이런 쉬운 문제 가뿐히 푸시는 분들은 지나가줘요..

[문제]

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

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

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

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

[입력]

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

[출력]

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

[예제 입력]

5
1 6
3 7
6 2
7 100
9 635
# 글쓴이 추가 100 100

[예제 출력]

1
7
6
1
9
# 10

[생각]

1) 처음에 든 생각은 이 문제가 왜 브론즈2지?? 였다.

그냥 a^b % 10을 출력하고, 만약 그 값이 0이면 10을 출력하는 되는 문제였기 때문이다.

하지만, 그대로 풀고 제출해보니, '시간 초과'가 나왔다. 왜지??

그래서 구글링을 해보니, a^b에서 a=9, b=999,999 인 경우를  생각해보라는 것이었다.

->정말 엄청난 수가 나오고, 이 경우 컴터 메모리를 초과할 수 있다는 것을 깨달았다...

2) 따라서 알고리즘을 다시 짜야했다.

for문 돌리는 동안 반환 값이 계속 작은 숫자로 남게 하면 되지 않을까?

이 생각을 바탕으로 재귀식을 짰다.(결과 값이 다시 입력값으로 들어가게 하는..

그런데 이렇게 짠 코드도 결국, b의 값이 엄청 커지면, 계산을 많이 해야했기에

'시간 초과' 가 나왔다.

-> 즉,  수 만번을 돌리며 계산하는 알고리즘을 피해야했다!

3) 곰곰히 생각하는 시간을 가졌다.(자연수 곱에 대하여)

거듭 제곱에서 1의 자리는 순환함을 기억했다.

1 -> 1 -> 1...

2 -> 4 -> 8 -> 6 ->2

3 -> 9 -> 7 -> 1 ->3

.

.

.

9 -> 1  -> 9

• 일의 자리 숫자에 따라서 거듭제곱할 때 규칙성을 가지는 것을 이용하고자 함(a%10 값 이용)
  • 일의 자리가 한 숫자로 반복되는 경우(0, 1, 5, 6)
  • 일의 자리가 두 숫자로 반복되는 경우(4, 9)
  • 일의 자리가 네 숫자로 반복되는 경우(2, 3, 7, 8)
• 일의 자리 숫자가 한 숫자로 반복되는 경우에는 b가 무슨 값이든 그냥 그 값을 출력해주면 된다.
  • 단, 0인 경우에 출력값은 10
• 일의 자리 숫자가 두 숫자로 반복되는 경우, b % 2 의 값에 따라 두 가지의 값을 출력해주면 된다.
  • 4의 경우(9의 경우도 마찬가지)
    • b % 2 == 1 일 때, 출력 값: 4
    • b % 2 == 0 일 때, 출력 값: 6
• 일의 자리 숫자가 네 숫자로 반복되는 경우, b % 3 의 값에 따라 네 가지의 값을 출력해주면 된다.
  • 2의 경우(3, 7, 8의 경우도 마찬가지)
    • b % 4 == 1 일 때, 출력 값: 2
    • b % 4 == 2 일 때, 출력 값: 4
    • b % 4 == 3 일 때, 출력 값: 8
    • b % 4 == 0 일 때, 출력 값: 6
• 단, 인덱싱 과정에서 b % 4 == 0 일 때, 맨 뒷 값을 인덱싱 할 수 있도록 변수 조정하는 것이 중요했다.!

[코드]

• 시간초과 코드1

• 시간초과 코드2

• 성공한 코드

[공부한 점]

• 알고리즘을 짜는 과정에서 항상 런타임도 생각해야함을 알았다.
  • 초반에는 왜 시간 제한이 있는지 몰랐으나, 그 이유를 알았다.
• 같은 문제라도 알고리즘에 따라서 엄청나게 시간이 많이 차이남을 깨달았다.
  • 조만간 알고리즘을 공부할 것인데, Big O에 대한 공부 동기부여를 미리 받은 느낌이다.
• 입력 값에 엄청나게 큰 숫자가 있으면 문제를 있는 그대로가 아닌, 필요한 데이터만 남기면서 반복문을 진행하여 풀어봐야겠다는 생각이들었다.