JArchive 프로그래밍 일기

문제

분산처리 백준 1009번

리뷰

제곱을 했을 때 가장 마지막 자리의 숫자가 뭔지 출력하면 되는 문제다.

b의 입력 조건이 큰 것을 감안해야 한다.

제곱을 하는 와중에도 '마지막 자리 수'만 잘라내서 제곱을 해야 int 범위를 넘지 않는다.

그래서 temp = temp * a 이렇게 제곱을 한 다음에 %10 나머지 연산을 통해 마지막 숫자를 잘라냈다.

for(i = 2; i <=b; i++){
    temp = temp * a % 10; // 마지막 자리 숫자 잘라내기 
}

이렇게 해도 자꾸 '틀렸습니다' 가 뜨길래 문제 해설 포스팅을 찾아봤다.

힌트는 제곱을 했을 때 4번 주기로 같은 숫자가 나온다는 것이었다.
2^1 = 2
2^2 = 4
2^3 = 8
2^4 = 6 (마지막 자리 숫자만 씀)
2^5 = 2
2^6 = 4

이렇게 2, 4, 6, 8 이 반복된다.

(4번째 제곱수마다 마지막 자리숫자들이 똑같이 반복되는 것을 이용한다. )

그래서 제곱 횟수 b를 % 4 연산을 했고, b가 0이 되는 것을 방지하기 위해 + 4를 해준 것이다.

b = b % 4 + 4; 

제곱횟수 b를 mod 연산을 하니까 그제서야 문제를 맞혔다. 아 개운하다 다음에 다시풀어봐야지 :)

코드

#include <stdio.h>
using namespace std;

// 분산처리 (BOJ 1009번) 

int main(void){

    //freopen("input.txt", "rt", stdin);

    int tc = 0, a = 0, b = 0;
    int temp = 0, i = 0; 

    scanf("%d", &tc);

    while(tc--){
        scanf("%d %d", &a, &b);

        temp = a;

        b = b % 4 + 4;  // b가 0이 되는 것을 방지하려고 +4 한다. 

        for(i = 2; i <= b; i++){ // 마지막 자리 숫자만 잘라낸다 
            temp = temp * a % 10;
        }

        if(temp == 0)
            temp=10;

        printf("%d\n", temp);
    }

    return 0;
}

참고 포스팅

크레이 님의 분산처리 문제 해설

크레이 님의 친절한 포스팅 감사합니다! :)