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

풀이는 아래와 같다.

#include <iostream>
// #include <cmath>
 
using namespace std;
 
int a[1000000];
 
int main(){
    
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    int n;
    // int* a = new int[n];
    int b, c;
    
    cin >> n;
    for( int i=0; i<n; i++){
        cin >> a[i];
    }
    cin >> b >> c;
    
    // int sum = 0;
    long long sum = 0;
    
    for( int i=0; i<n; i++){
        if(b >= a[i]){
            sum += (long long)1;
        // }else if (b + c >= a[i]){
        //     sum += 2;
        }else{
            // sum += ceil((float)(a[i]-b)/c) + 1;
            
            if( (a[i]-b)%c == 0){
                sum += (long long)((a[i]-b)/c + 1);
            }else{
                sum += (long long)((a[i]-b)/c + 2);
            }
        }
    }
    
    cout << sum << '\n';
    // delete[] a;
    return 0;
    
}

시행착오:

처음에는 알고리즘이 틀린줄 알고, 혹은 a의 배열이 동적할당을 하면 안되나(?) 싶어서 주석 처리를 하고 전역 변수로 a를 int형 배열로 선언해주었는데, 그게 문제가 아니었던 것 같다. 메모리가 스택 영역에 생성되는 건 함수 내에서 그냥 선언되어 사용하는 배열의 경우인데, 이게 너무 크면 문제가 되지만 동적할당한 경우에는 괜찮은 것 같다. 근데 또 동적할당할때는 runtime error(Segfault)가 뜨더니 전역변수로 선언하니까 틀렸습니다! 라고 떠서 그 차이가 왜 생기는지는 나중에 알아봐야겠다. 그리구 아래는 검색하다가 알게 된 내용이지만 앞으로도 참고하면 좋겠다.

 

"배열의 크기가 꽤 큰 것 같은 생각이 든다면 함수 내에서 선언하는 것보다 전역 변수로 선언하여 스태틱 영역을 사용하거나 동적 할당을 하여 힙 영역의 메모리를 이용하자."

 

암튼 위와 같은 가르침을 얻긴 했지만 그게 문제가 아니었다. 문제는 바로 sum의 자료형에 있었다.

처음에 int형으로 선언했는데, 도저히 왜 틀렸는지 알수가 없어서 찾아보는 과정에서 충격적이게도

long long 이라는 자료형이 있음을 발견했다. 왜 나는 아직까지 몰랐던 건지..? PS가 처음이라 그런지 이전에 수업을 들을때는 필요없었던 자료형을 검색하다 알게 되었다. 사실 별건 아니고 64비트 머신의 long형이 8byte라 그걸 이르는 자료형인거 같긴 한데 나중에 주말에 시간 많을때 더 알아봐야겠다. 그냥 long은 컴퓨터가 32비트인지 64비트인지 여부에 따라 4byte, 8byte로 달라지는 걸로 알고 있는데 long long 은 __int64 같은 느낌인거 같다. 암튼 이 sum의 자료형을 바꾸어 주니 성공했다...! 감독관의 총 수로 가능한 최댓값이 백만 곱하기 백만임을 감안하면 이 생각을 할만도 한 것 같다. 문제가 어쩐지 너무 간단하더라니 역시 알고리즘 문제를 풀 때는 큰 수를 다루는 것이 점점 익숙해져야겠다는 생각이 든다. 오늘도 겸손해지는 하루인 것 같다... 더 열심히 해보자 빠팅!