C++로 2^n의 마지막 두 자리 숫자 구하는 프로그램

이 문제에서는 하나의 숫자 N이 주어지며, 우리의 목표는 C++를 사용해 2^n의 마지막 두 자리 숫자를 구하는 프로그램을 작성하는 것입니다.

문제 설명

마지막 두 자리 숫자만 구하면 되기 때문에, 계산 과정에서도 마지막 두 자리 숫자만 곱셈에 활용하고 나머지 값은 버려서 연산량을 최소화할 수 있습니다.

예시를 통해 문제를 이해해 보겠습니다.

입력: N = 12

출력: 96

설명

2^12 = 4096이므로, 마지막 두 자리인 96이 결과가 됩니다.

풀이 접근 방법

가장 직관적인 방법은 2^N 값을 직접 계산한 뒤, 그 값을 100으로 나눈 나머지를 구하는 것입니다.

예제 코드

#include <iostream>
using namespace std;
int findLastDigit(int N){
    int powerVal = 1;
    for(int i = 0; i < N; i++){
        powerVal *= 2;
    }
    return powerVal%100;
}
int main() {
    int N = 14;
    cout<<"2^"<<N<<"의 마지막 두 자리 숫자는 "<<findLastDigit(N);
    return 0;
}

출력 결과

2^14의 마지막 두 자리 숫자는 84

하지만 이 방식은 비효율적입니다. N의 값이 커지면 2^N이 int 자료형의 범위를 초과하는 오버플로우(overflow)가 발생하기 때문입니다.

더 효율적인 접근 방법

더 나은 방법은 전체 값이 아닌 마지막 두 자리 숫자만 유지하면서, 매 거듭제곱마다 2를 곱하고 100으로 나눈 나머지를 취하는 것입니다.

예를 들어 2^14의 마지막 두 자리가 84라면, 다음 단계에서는 전체 숫자가 아닌 84에 2를 곱합니다. 즉, (84 × 2) % 100 = 68이 되어 계산량을 크게 줄일 수 있습니다. 이렇게 하면 어떤 큰 N에 대해서도 오버플로우 없이 정확한 답을 구할 수 있습니다.

예제 코드

#include <iostream>
using namespace std;
int findLastDigit(int N){
    int powerVal = 1;
    for(int i = 0; i < N; i++){
        powerVal = (powerVal * 2)%100;
    }
    return powerVal;
}
int main() {
    int N = 15;
    cout<<"2^"<<N<<"의 마지막 두 자리 숫자는 "<<findLastDigit(N);
    return 0;
}

출력 결과

2^15의 마지막 두 자리 숫자는 68

이처럼 모듈로(modulo) 연산을 활용하면 지수가 아무리 커져도 항상 안정적으로 마지막 두 자리 숫자를 구할 수 있습니다.