1009번... 런타임 오류만 수 없이 떠서 고생했습니다.
총 10대의 컴퓨터는 각각 1개의 데이터를 처리하는 역할을 합니다.
1=1, 2=2, 3=3, 4=4,... 10=10
조건
입력의 첫 줄은 테스트를 진행활 횟수를 입력 받는다.
다음 줄부터 테스트할 정수 a, b를 한 번의 엔터로 입력한다.
마지막 데이터를 처리할 컴퓨터의 번호를 출력한다.
예외처리까지 삽입해서 해결해 보려고 했는데 런타임 오류가 없어지질 않아서...
오로지 문제만 해결할 수 있는 코드를 작성해 보았습니다.
(공부할 겸 예외처리도 만들어 보았습니다.)
접근
먼저 연속된 a와 b의 값을 받기 때문에 리스트 형식으로 만들기로 했습니다.
이후 출력도 for문으로 연속해서 출력할 수 있는 이점을 활용한 겁니다.
1. 빈 리스트를 만들고
2. 리스트의 마지막 위치에 값을 삽입하는 append() 함수를 활용
a = 밑수 b = 지수 t = 케이스의 개수
이번이 중요합니다...!
런타임 오류를 해결했지만 시간 초과의 늪에 빠질 수 있기 때문입니다.
예제 입력처럼 7^100과 9^635는 상당히 높은 값을 발생시킵니다.
프로그램이 이 연산을 그대로 수행하면...
시간 초과를 벗어날 수 없습니다.
해답은 출제한 문제에 있었습니다.
컴퓨터가 10대이기 때문에 사이클은 10으로 돕니다.
즉 일의 자리 수 = 데이터 처리 컴퓨터
일의 자리 0은 10번 컴퓨터와 같습니다.
그리고 지수가 아무리 커져도 일정한 규칙이 발생합니다.
3과 5를 예로 들어보겠습니다.
3^1=3 3^2=9 3^3=27 3^4=81 3^5=243...
5^1=5 5^2=25 5^3=125...
일의 자리 값만 보시면 일정한 규칙이 발생함을 확인할 수 있습니다.
이를 코드에 적용하면 시간 초과 오류를 해결할 수 있습니다.
밑수(값의 일의 자리)가 0, 1, 5, 6이면 지수가 어떤 값이든 밑수와 같습니다.
하지만 0의 경우는 10번 컴퓨터를 의미해야 하기 때문에 따로 조건을 답니다.
1, 5, 6은 같은 조건을 달도록 합니다.
4와 9는 두 값이 반복됩니다.
즉 지수를 2로 나누었을 경우 나머지가
1이 나오면(지수가 홀수일 때) 4와 9를,
0이 나오면(지수가 짝수이면) 6과 1을 뽑아냅니다.
(ex. 4^1=4, 4^3=64 9^2=81 9^4=6561)
2, 3, 7, 8도 같은 형식으로 접근합니다.
지수 값이 어떻든 결과는 4개씩 반복됩니다.
즉 일의 자리만 보았을 때
3^1 = 3^5 = 3^9...입니다.
코드 해석
base는 밑수가 10 이상의 값일 경우 일의 자리로 단축시킨 값을 저장합니다.
그 값이 0이라는 것은 a가 10의 배수라는 뜻이고 이는 모두 10번 컴퓨터가 처리합니다.
base(일의 자리)가 1, 5, 6일 경우 어떤 지수든 값은 base(일의 자리)와 같은 값이 나옵니다.
base(일의 자리)가 4, 9일 경우 어떤 지수든 2개의 값이 반복됩니다.
즉 지수가 짝수(2,4,6,8...) 일 경우 모든 결과의 일의 자리는 a^2를 한 값과 같습니다.
지수가 홀수(1,3,5,7...) 일 경우는 모든 결과가 base(일의 자리)와 동일합니다.
다만 지수를 2로 나눈 나머지를 적용시키면 0으로 인식되어 런타임 오류가 발생하기 때문에
출력 값에 2를 직접 나누기 연산하도록 합니다.
base(일의 자리)가 2, 3, 7, 8일 겨우 어떤 지수든 4개의 값이 반복됩니다.
지수가 4의 배수라면 a^4를 한 값과 같듯이
나머지들도 다 a^1, a^2, a^3을 한 값과 동일합니다.
다만 지수를 4로 나눈 나머지를 적용시키면 0으로 인식되어 런타임 오류가 발생하기 때문에
출력 값에 4를 직접 나누기 연산하도록 합니다.
접근과 코드 해석 부분을 잘 읽어보시어 이해에 도움이 되었으면 좋겠습니다.
-끝-
'작업 > Problem Solving' 카테고리의 다른 글
| 백준 9498번(시험 성적) 파이썬(python)으로 해결 (0) | 2020.07.19 |
|---|---|
| 백준 1011번(Fly me to the...) 파이썬(python)으로 해결 (0) | 2020.01.18 |
| 백준 1010번(다리 놓기) 파이썬(python)으로 해결 (0) | 2020.01.17 |
| 백준 2588번(곱셈) 파이썬(python)으로 해결 (0) | 2020.01.14 |
| 백준 1008번(A/B) 파이썬(python)으로 해결 (0) | 2020.01.14 |
