인프런 커뮤니티 질문&답변
작성한 질문수
1 - N번 질문 있습니다.
작성
·
186
0
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll a,b,c;
ll go(ll a, ll b){
if(b == 1){return a % c;
ll _c = go(a, b/2);
_c = (_c * _c) % c;
if(b % 2) _c = (_c * a) % c;
return _c;
}
}
재귀 부분에서 _c의 값을 어떻게 결정하는건가요??
_c = (_c * _c) % c 이라면 값을 결정할 수 없는거 아닌가요ㅜㅠ
답변 2
1
큰돌
지식공유자
안녕하세요. ㅎㅎ
예를 들어 go(2)라는 함수가 2를 반환하는 함수라고 해보죠.
go(4)는 4를 반환하는 함수이구요.
go(2) * go(2) = go(4) 라는 꼴이 됩니다.
go(2) = 2이기 때문에
2 * 2 = go(4) 가 되죠?
이처럼 _c는 go 함수에 인자를 2로 나눈 값을 기반으로 호출된 값이 들어가게 됩니다.
_c와 b를 함수별로 출력해보면서
ex) cout << _c << '\n'
디버깅을 해보시면서 보시면 충분히 이해가 가실겁니다.
감사합니다.
0
큰돌
지식공유자
안녕하세요. ㅎㅎ
그니까 _c = (_c * _c) % c; 이게 작동을 안한다. 라는 말씀이신가요?
예를 들어
x = 2;
x = x * x
이게 작동을 안한다라는 건가요?
안녕하세요!
이해가 안되는 부분이
go 함수에 a, b가 들어가면 _c는 go(a, b/2)가 되잖아요
b가 짝수라면 다음 식은 _c = (_c * _c) % c 인데 _c에 어떤 값이 들어가는지 감이 안와서 질문 드렸습니다..@