D3 - 8840. 아바바바

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AW4Z8x2KAL8DFAQ7&categoryId=AW4Z8x2KAL8DFAQ7&categoryType=CODE#none

SW Expert Academy

문제 설명

---

‘a’와 ‘b’가 번갈아 나오는 길이 L인 문자열이 있다. L = 5이면 “ababa”이고, L = 7이면 “abababa”이다.

홀수 L이 주어질 때, ‘a’와 ‘b’가 번갈아 나오는 길이 L인 문자열에서, 

길이가 2이상인 연속한 부분 문자열이 회문(앞으로 읽어도 뒤로 읽어도 같은 문자열)인 것의 개수를 구하는 프로그램을 작성

 

 

 

문제 풀이

---

홀수이므로 규칙을 만들어 보면 2n+1인 홀수의 개수. 즉, 2n+1을 만족하는 n의 제곱이 답이 된다. 홀수의 합은 홀수의 개수의 제곱

 

 

 

코드

---

이번 문제풀이에서 중요한 핵심은 라이브러리에서 cmath의 pow 함수의 속도보다 기본적인 방법이 속도가 빠른 측면이 있다. 간단한 수학 계산인 경우. 따라서 시간 초과가 발생한 코드와 시간 초과가 발생하지 않은 코드 두 개가 존재합니다.

#include <iostream>
#include <cmath>
using namespace std;
int main()
{
    cin.tie(NULL);
    cout.tie(NULL);
    ios_base::sync_with_stdio(false);
    int test_case,n;
    long long ans;
    cin>>test_case;
    for (int t=1;t<=testcase;t++)
    {
        cin>>n;
        long long temp = (n-1)/2;
        cout<<"#"<<t<<' '<<temp*temp<<'\n';
    }
    return 0;
}

시간 초과가 발생한 코드

#include <iostream>
#include <cmath>
using namespace std;
int main()
{
    cin.tie(NULL);
    cout.tie(NULL);
    ios_base::sync_with_stdio(false);
    int test_case,n;
    long long ans;
    cin>>test_case;
    for (int t=1;t<=testcase;t++)
    {
        cin>>n;
        long long temp = (n-1)/2;
        cout<<"#"<<t<<' '<<pow(temp,2)<<'\n';
    }
    return 0;
}

 

 

funny algorithms :) ~