들어가며

백준 1009번 문제를 풀며 놓친 부분을 정리해 보려고 합니다.

---

문제 풀이

1009번 문제는 주어진 총 데이터 개수의 1의 자리를 구하는 문제입니다. 단, 주어진 b의 크기가 크기 때문에 a^b에 1의 자리를 바로 구할 수는 없습니다.

문제를 읽고 나서 가장 먼저 들었던 생각은 b의 크기를 줄여야겠다는 것입니다. 그럼 b의 크기를 어떻게 줄일 수 있을까요?

총 데이터의 개수가 a에 거듭제곱의 형태를 취하고 있기 때문에 우리는 1의 자릿수를 미리 예측해 볼 수 있습니다.

• a에 1의 자릿수가 1인 경우, a에 거듭제곱의 1의 자릿수는 항상 1입니다.
• a에 1의 자릿수가 2인 경우, a에 거듭제곱의 1의 자릿수는 2, 4, 8, 6이 반복됩니다.
• a에 1의 자릿수가 3인 경우, a에 거듭제곱의 1의 자릿수는 3, 9, 7, 1이 반복됩니다.
• 표로 만들 경우 아래와 같은 표를 만들 수 있습니다.

1	2	3	4
1	1	1	1
2	4	8	6
3	9	7	1
4	6	4	6
5	5	5	5
6	6	6	6
7	9	3	1
8	4	2	6
9	1	9	1

예측해 본 1의 자릿수를 보게 되면 1의 자릿수가 반복되는 최대 횟수는 4번이라는 것을 알 수 있습니다. 따라서, b를 4로 나눈 나머지를 알면 a^b에 1의 자릿수를 알 수 있습니다.

코드로 구현해 제출했더니 바로 틀렸습니다. 뭘 놓친 걸까요? b가 4의 배수인 경우와 a^b이 10의 배수인 경우를 놓쳤습니다. 이를 반영해 코드를 다시 작성하니 이번에는 맞출 수 있었습니다.

Code

#include <iostream>
#include <vector>
#include <cmath>

using namespace std;

int main()
{
    // 테스트 케이스의 개수 T를 입력 받는다.
    int T;
    cin >> T;

    // 답을 저장할 vector를 초기화한다.
    vector<int> answer(T);

    for (int& result : answer) {

        // a와 b를 입력 받는다.
        int a, b;
        cin >> a >> b;

        // b가 4의 배수인 경우와 a^b이 10의 배수인 경우를 고려해 삼항연산자로 처리한다.
        b = b % 4 ? b % 4 : 4;
        result = (int)pow(a % 10, b) % 10;
        result = result ? result : 10;
    }

    // 답을 출력한다.
    for (const int& a : answer) {
        cout << a << endl;
    }

    return 0;
}

---

포스팅을 마치며

오랜만에 문제를 다시 풀어보니 간단한 문제에서도 실수가 나오네요.
오답 노트를 꾸준히 기록해 실수를 줄여나가겠어요.

Reference

hellodj. Baekjoon 1009번 분산처리. Baekjoon.