[C++, 코딩테스트] Softeer : 지도 자동 구축

Softeer - 현대자동차그룹 SW인재확보플랫폼

 

문제는 위 링크에서 확인바란다.

 

일단 이 문제는 패턴을 파악해서 수식화하는 능력을 요구한다.

 

첫번째 네모의 한 변에 있는 점의 개수는 2개, 다음은 3개, 다음은 5, 9, 17 ...

 

이렇게 늘어나는데 패턴은 

 

 

#include<iostream>
#include<cmath>

using namespace std;

int main(int argc, char** argv)
{
    int N;
    cin >> N;

    long long lineCount = 2;
    for (int i = 0; i <= N - 1; i++){
        lineCount += pow(2, i);
    }

    cout << lineCount * lineCount << endl;
    return 0;
}

 

 

여기서 주의할 점이 있다. 처음에는 pow를 사용해서 값을 출력했는데

 

cout << pow(lineCount, 2) << endl;

 

N = 10일 때의 결과 값을 출력하니까

 

 

위 사진 처럼 다르게 표현되는 것을 알 수 있다. 이 이유는 pow는 부동 소수점을 이용해서 계산하기 때문이다.

 

부동 소수점과 고정 소수점의 개념을 알아야하는데, 간단하게 말하면 부동 소수점은 큰 숫자와 소수점이 있는 실수를 나타내는데 좋은 방식이고 고정 소수점은 정수를 나타내는데 좋은 방식이다.

나타라서 위 문제는 정수만을 나타내니까, 더 넓은 정수를 나타낼 수 있는 방식인 고정소수점 방식을 사용하는 것이다. 좋다.

 

부동 소수점과 고정 소수점이 데이터를 저장하는 방식을 bit 단위로 공부해 보면 좋을 것이다.

 

따라서 N이 더 커질 수 있으니까 pow는 사용 안하는게 좋을 것 같다. 근데 또 N이 더 커지면 정수 크기 범위를 넘어가는 상황이 생길 수 있으니까 long long으로 바꿔야 한다. 그래서 만약 N이 15보다 커서 2의 N승이 int 범위를 넘어 갈 수 있다면

 

#include<iostream>
#include<cmath>

using namespace std;

int main(int argc, char** argv)
{
    int N;
    cin >> N;

    long long lineCount = 2;
    long long mul = 1;
    for (int i = 0; i < N; i++){
        if (i == 0)
            mul = 1;
        else 
            mul *= 2;
        lineCount += mul;
    }
    cout << lineCount * lineCount << endl;
    return 0;
}

 

 

이런 식으로 long long 타입과 pow 대신 dp를 이용하여 곱을 저장하는 방식으로 해야한다.