ray

ray

매일의 HIGHLIGHT를 찾아서 ✨

[백준] 1009 분산처리 (C++)

Posted on Feb 2, 2021 #구현   #Algorithm  

1009 | 분산처리

🙋‍♀️ 문제

재용이는 최신 컴퓨터 10대를 가지고 있다. 어느 날 재용이는 많은 데이터를 처리해야 될 일이 생겨서 각 컴퓨터에 1번부터 10번까지의 번호를 부여하고, 10대의 컴퓨터가 다음과 같은 방법으로 데이터들을 처리하기로 하였다.

1번 데이터는 1번 컴퓨터, 2번 데이터는 2번 컴퓨터, 3번 데이터는 3번 컴퓨터, … ,

10번 데이터는 10번 컴퓨터, 11번 데이터는 1번 컴퓨터, 12번 데이터는 2번 컴퓨터, …

총 데이터의 개수는 항상 ab개의 형태로 주어진다. 재용이는 문득 마지막 데이터가 처리될 컴퓨터의 번호가 궁금해졌다. 이를 수행해주는 프로그램을 작성하라.

🙌 입출력

입력의 첫 줄에는 테스트 케이스의 개수 T가 주어진다. 그 다음 줄부터 각각의 테스트 케이스에 대해 정수 a와 b가 주어진다. (1 ≤ a < 100, 1 ≤ b < 1,000,000)

각 테스트 케이스에 대해 마지막 데이터가 처리되는 컴퓨터의 번호를 출력한다.

🙋‍♂️ 예제 입출력

5
1 6
3 7
6 2
7 100
9 635

1
7
6
1
9

a%10==0 일때 10 출력

1
20 1

10

오버플로우 확인 시 사용

1
97 999

3

🚀 코드

#include <iostream>
#include <vector>
using namespace std;

void func(int a, int b) {
	int rst = 0;
	int num = a * a;
	vector<int> v;
	v.push_back(a % 10); // a의 끝자리 수를 먼저 배열에 삽입

	// 이 반복문에서는 a^b의 끝자리 수(1의 자리수)의 반복 수열을 구한다
	// ex) 3의 경우, [3, 9, 7, 1]
	while (true) {
		if (num % 10 == v[0]) { // 끝자리수가 같으면 탈출
			break;
		}
		v.push_back(num % 10);
		num = (num % 10) * a; // 여기서 오버플로우> 97 999
	}
	int idx = b % v.size();
	if (idx == 0) {
		idx = v.size();
	}
	rst = v[idx - 1];
	if (rst == 0) {
		rst = 10;
	}
	cout << rst << '\n';
	// endl 보다 '\n'이 더 빠름
	return;
}

int main() {
	int n, a, b = 0;
	cin >> n;
	int rst = 0;
	int last = 0;
	for (int i = 0; i < n; i++) {
		cin >> a >> b;
		func(a, b);
	}

	return 0;
}

🌠 메모

처음 코드는 10분도 안걸려서 짠거 같은데 계속해서 틀렸다고 나와서 한참 헤맸다.

백준 질문란에 나와있는 코드를 봤는데 나처럼 푼 경우는 거의 못봤다. 일단 내 아이디어는 a를 제곱하며 그 끝자리 수를 배열에 저장한다. (계산해보면 알겠지만 모든 숫자에 대해서 1, 2, 4개의 끝자리 수가 반복된다.)

이는 따로 math.h를 사용하고 싶지도 않았고, 반복문을 b만큼 돌기엔 시간이 오래 걸릴것으로 생각해서 while문에서 끝자리 수의 반복 패턴을 알아내면 바로 나오도록 했다. 따라서 최대 4번까지만 돌고 나온다. (1<= b < 1,000,000 여서 반복문 횟수를 줄이고 싶었다. 다른 사람들의 풀이를 보니 b %= 4 를 통해 나와 같이 횟수를 줄인 것으로 보인다.)

idx는 b % v.size()의 값을 할당하고 이 값이 0 일 경우는 v.size()로 재할당 하여 이후 v[idx-1]에서 의도한 값이 나오도록 했다.

또한 가장 흔한 반례를 통해, rst 값이 0인 경우에는 10 번 컴퓨터 번호를 출력하도록 해주었다.

여기까지 했는데도 정답이 아니어서 한참동안 질문글을 검색하고 반례를 넣어보며 삽질하다가 겨우 틀린 부분을 알아냈다. 끝자리 수 배열을 구하기 위해 num = num * a을 해주며 반복문을 도는데, 만약 a가 100에 가까운 큰 수라면 4번을 채 돌기전에 오버플로우가 생겨버린다. 필요한 값은 1의 자리수 뿐이므로 num = (num % 10) * a로 수정했다.

앞서 풀었던 13305번 주유소문제에서도 이미 자료형 범위로 인해 애먹었던 기억이 있어 이번에는 더 주의했는데, a, b의 범위에만 집중하다 보니 코드를 짜면서 발생할 수 있는 오버플로우에 대해서는 신경쓰지 못한 것 같다.



# 카테고리