[C++]백준 알고리즘 2839번

풀이는 아래와 같다.

 

#include <iostream>
 
using namespace std;
 
int sugar(int);
 
int main(){
    
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    int n;
    cin >> n;
    cout << sugar(n) << '\n';
    
    return 0;
}
 
int sugar(int a){
    if( a == 3 || a == 5){
        return 1;
    }else if ( a == 4){
        return -1;
    }else{
        switch (a % 5){
            case 0:
                return a / 5;
                break;
            case 1:
                return (a-6)/5 + 2;
                break;
            case 2:
                if( a-12 >= 0 ) return (a-12)/5+4;
                else return -1;
                break;
            case 3:
                return (a-3)/5 + 1;
                break;
            case 4:
                return (a-9)/5 + 3;
                break;
        }
    }
    return 0;
}
 
 
// int sugar(int a){
//     if(a == 3 || a == 5){
//         return 1;
//     }else if (a < 5){
//         return -1;
//     }else{
//         int b = sugar(a-5);
//         int c = sugar(a-3);
//         if(b > 0){
//             return b + 1;
//         }else if(c > 0){
//             return c + 1;
//         }else{
//             return -1;
//         }
//     }
// }

시행착오:

처음에 문제를 풀었을 때는 시간초과가 떴는데, 이유는 아래의 주석처리된 부분과 같이 recursive 함수를 썼기 때문이다. 재귀함수는 해답 자체를 찾는데는 유용할 때가 많지만 시간이 대체로 iterative 과정보다 더 오래 걸리는 것이 알려져있다. 확실하지 않지만 재귀함수를 사용한 것 자체가 문제였을 것 같다. 따라서 문제를 잘 분석해보니 5로 나눈 나머지를 기준으로 수를 분류한다면 훨씬 더 간단하게 답을 구할 수 있음을 깨달았다. 그렇게 식을 위의 sugar 함수처럼 고쳐서 제출하니 맞았다고 떴다.

 

이 한 문제를 풀었더니 랭크가 2천등을 올라가는 걸 보니 이제 겨우 시작이다 생각이 들면서도 뭔가 동기부여가 되는 것 같다. 나는 항상 중고등학교 때부터 경쟁을 통해 성취감과 열정을 찾았던 것 같기도 하다. 열심히 계속 해보자!!! 빠팅 ㅎㅎ