[SWEA 884][C++] 아바바바(D3)

[문제보기]

 8840. 아바바바

SW Expert Academy

 

[풀이과정]

 cin.tie(0);

 cout.sync_with_stdio(false);

 이 두 줄을 넣음으로 인해서 cin, cout이 연산이 빨라져 시간안에 들어올 수 있다.

 

 dp로 맨 처음에 모든 수에 대한 결과를 먼저 생성 후에 각 입력값에 따라 출력을 해줄려고 했지만,

 생각을 해보니 각각 입력값에 대해 바로바로 계산을 하는 쪽으로 방향을 바꿨다. 이로 인해 

 dp로는 최대 10억에 대해서 한번씩 계산을 해줘야되지만, 나중에 생각한 방식으로는 테스트케이스에 있는

 10만개만 계산을 하면 된다.

 

 n = 3 일 때,

 aba => (aba) 1개

 

 n = 5 일 때,

 ababa => (aba, bab, aba, ababa) 4개

 

 n = 7 일 때,

 abababa => (aba, bab, aba, bab, aba, ababa, babab, ababa, abababa) 9개

 

 로 계산이 되므로 ((n-1)/2)^2 이라는 점화식이 만들어진다.

 

[소스코드]

#include <iostream>
using namespace std;

int main(){
    cin.tie(0);
    cout.sync_with_stdio(false);

    int T;
    cin >> T;
    for(int test = 1; test <= T; test++){
        int n;
        cin >> n;
        long temp = (n-1)/2;
        cout << "#" << test << " " << temp*temp << "\n";
    }
}

 

[해결과정 중 실수 한 부분]

 맨 처음의 코드로 제출을 했을때, 테스트케이스중에서 112개만 맞고 나머지는 계속 틀리다고 나왔다. 

 코드를 다시 봤는데 로직상으로는 틀린점이 없어 문제를 다시 살펴보는데, L의 숫자의 범위가 10억이라는 것을 보고

 int 형이 아니라 long을 써야된다고 생각이 들어 고쳐서 pass를 받았다.