인프런 커뮤니티 질문&답변
작성한 질문수
시간복잡도 Q3 문제 질문
작성
·
235
0
안녕하세요!
시간복잡도 Q3 문제에서 cnt로 디버깅해서 cnt 값이 19 39 이런식으로 나오니까 2n-1을 도출해내서 시간복잡도를 구하셨는데 해당문제를 Q5 문제처럼 점화식을 찾아서 그 공식으로 나온 결과가 2n-1을 도출해내는 풀이도 있을까요?
답변 1
0
큰돌
지식공유자
음... 제가 Q5문제 또한.. 이렇게 cnt로 디버깅해서 했는데요.
혹시 어떤 부분이 질문이신가요?
#include<bits/stdc++.h>
using namespace std;
int N, cnt;
void solve(int N){
cnt++;
cout << cnt << '\n';
if(N == 0) return;
for(int i = 0; i < 3; i++){
solve(N - 1);
}
return;
}
int main(){
cin >> N;
solve(N);
return 0;
} 
Q5 문제는 그림을 그려서 1 + 3 + 27 .. 이라는 규칙을 찾고 등비수열의 합이라는 점화식을 도출해내신거처럼 Q3 문제도 같은 방법으로 점화식을 도출할 수 있을까해서요