백준 1011 Fly me to the Alpha Centauri 분석

 

#include <iostream>
using namespace std;
int T;
bool check;
int func(long long x,  y, int k){
    
    if(x == y-1){ return 1; }
    else if( x > y-1){ return 0; }
    int count = func(x+k+1, y, k+1);
        count += func(x+k,   y, k  );
    return count;
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    long long x,y;
    cin >> T;
    while(T--){
        cin >> x >> y;
        check = false;
        if( y-x == 1) cout << 1 << '\n';
        else cout << func(x, y, 1)+1 << '\n';
    }
}

애초에 이 글을 읽는 분들은 문제는 이미 읽고 왔을 거라 생각하여 문제 분석만 하겠습니다.

x와 y값은 무엇이 되든 상관이 없으며, x와 y의 사이 값 즉 뺀 값만 유의미합니다.

또한 규칙으로 처음 시작은 1로 시작이 가능하며 뒤에서도 1로 끝나야 합니다.

일단 먼저 앞에서부터 뒤로 가며 체크해나가는 코드를 짜보았습니다.

값도 제대로 출력되며 잘 됩니다.

물론

시간초과가 떴습니다.

재귀니까 역시 느립니다. 지난번까지 별만 찍다보니 재귀에 맛들려버려 아니 재귀적인 사고방식이...

익숙해진걸까 역시 생각하기 쉬운 것 같습니다.

물론 시간초과니 틀렸습니다. 그래서 이미 글러서 다른 분의 영상을 보고 이해해보았습니다.

애초에 하나씩 할 필요가 없는 문제였다는 사실에 슬펐습니다.

앞에서 뒤로 가는 것이 아닌 앞 뒤로 하나씩 증가시켜 보는 것이었습니다.

1, 2, 3, 4, 4, 3, 2, 1이런 식으로 하는 것이었고, 이런 식이 가능한 이유도 횟수만 파악하면 되기 때문이었습니다.

그러니까 x의 값이 y의 값과 동일해지는 것은 무의미한 것이기 때문.. ㅜㅜ 실버 1인데 그래도 쉽네요.