https://www.acmicpc.net/problem/18291
문제
비요뜨는 지금 강 앞에 서 있다. 강 위에는 징검다리가 놓여 있다.
징검다리는 비요뜨가 있는 방향에서부터 반대 방향까지 차례로 1번, 2번, ..., N번의 번호를 가지고 있다.
비요뜨는 1번 징검다리 위에 올라갔다. 그리고 아래 두 가지 규칙을 지키며 징검다리를 건너려고 한다.
- 1 ≤ X ≤ N 인 임의의 정수 X에 대해, 현재 있는 징검다리의 번호를 i번이라고 할 때 i+X번 징검다리로 뛸 수 있다.
- N번째 징검다리를 지나쳐선 안 되고, 정확히 도착해야 한다
비요뜨는 자신의 특기인 코딩을 살리기 위해 노트북을 켰지만, 실수로 노트북을 강에 빠뜨리고 말았다.
비요뜨를 대신해 강을 건너는 경우의 수를 구해 주자!
입력
첫 번째 줄에 테스트 케이스의 수 T가 주어진다. (1 ≤ T ≤ 1000)
각 테스트 케이스는 한 줄로 구성되며, 징검다리의 개수를 의미하는 N이 주어진다. (1 ≤ N ≤ 109)
출력
각 테스트 케이스에 대해, 한 줄에 하나씩 규칙을 만족하면서 징검다리를 건너는 경우의 수를 109+7로 나눈 나머지를 출력한다.
예제ㅔ
조건
- 시간 제한: 1초
- 메모리 제한: 256MB
코드
초기 코드
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
mod = 1000000007
# 고속 거듭제곱 함수
def power(a,b):
if b == 1: # 1승이 될때까지 재귀
return a
else:
temp = power(a,b//2)
if b % 2 == 0:
return (temp*temp) % mod
else:
return (temp*temp*a) % mod
T = int(input())
for _ in range(T):
N = int(input())
if N == 1:
print(1)
else:
print(power(2,N-2))이 문제는
2^(N-2)를 계산해주면 되는 문제이다.
-
그러나 이 값은 매우 커질 수 있고, 그로 인해 시간이 오래 걸리므로 일반 거듭제곱이 아닌 고속 거듭제곱 함수를 만들어 사용해야 한다.
-
지수법칙을 이용하는 것이 원리이다.
함수에 (2,5)가 들어왔다고 가정해보자.
-
① 현재
b가 5이기 때문에, 이를 2로 나눈 후에 다시 재귀 호출한다. -
② 아직
b는 2로 1이 되지 않았기 때문에, 2로 나눈 후에 다시 재귀 호출한다. -
③ 이제
b가 1이 되었으므로,a즉 2를 리턴한다. -
③ 을 통해서 ② 는
temp에 2를 리턴받는다. 그리고 현재b는 2로 짝수이기 때문에,2 * 2 % mod를 리턴한다. 👉return (temp*temp) % mod -
② 를 통해서 ① 은
temp에 4를 리턴받는다. 그리고 현재b는 5로 홀수이기 때문에,(4 * 4 * 2) % mod를 리턴한다. 👉return (temp*temp*a) % mod -
홀수에서
a를 한 번 곱해주는 것은,b//2를 하는 과정에서 손실된 1만큼의 지수를 더 곱해주기 위함이다. -
(4 * 4 * 2)는(2^2 * 2^2 * 2)로 구하고자 하는2^5와 동일하다. -
이러한 과정을 통해서 계산을 효율적으로 행할 수 있다.
😂 처음에는
sys.setrecursionlimit(10**7)코드를 빼고 제출을 했더니,
런타임 에러 (RecursionError)가 떴다.
-
이 때문에 추가를 해서 제출을 하니, 이번에는
메모리 초과가 떴다... 이건 예상치 못한 것이라 구글링을 해보니,pypy는python에 비해 재귀에 약하다고 한다! -
그래서
python으로 냈지만..또 메모리 초과가 나 결국 다른 분의 코드를 참고해서 수정하여 맞출 수 있었다.
수정 코드
import sys,math
input = sys.stdin.readline
mod = 1000000007
def power(C,n): # 고속 거듭제곱
res = 1
while n:
if n % 2 != 0: # 홀수인 경우
res *= C
res %= mod # 값이 커짐을 방지하여, 연산시마다 나눠줌
C *= C
C %= mod
n //= 2
return res
T = int(input())
for _ in range(T):
N = int(input())
if N == 1:
print(1)
else:
print(power(2,N-2))하지만 솔직히 전 코드에 비해서 명확히 이해가 되지는 않는다 😥
- 그리고
N == 1인 경우에 답이 1인 것도 잘 이해가 되지는 않았지만, 징검다리가 아닌 강 앞에서 시작을 하므로(1)자체로 1개의 가지수가 될 수도 있겠다는 생각이 들었다.
느낀 점 & 배운 점
-
정답은 받았지만.. 분할 거듭제곱에 대한 공부가 더욱 필요할 것 같다는 생각이 들게 된 문제였다.
-
하지만 주로 쓰는
pypy가 재귀에 약하다는 것을 알게 되어, 앞으로 재귀 문제를 풀 때는python으로 제출을 하고, 꼭sys.setrecursionlimit를 통해서 재귀 깊이를 늘려주어야겠다는 유익한 정보도 얻은 좋은 문제였다!
