[백준/C++] 1009번. 분산 처리

문제

1009번: 분산처리

---

1. 첫 번째 풀이

사고 과정

- 길게 늘여썼지만, 결국 a^b의 1의 자리 수를 구하는 문제.

- 단, b가 최대 1,000,000인 만큼 연산자만 사용하면 계산할 수 없다.

- 모듈러 연산을 안다면 순식간에 풀 수 있다. 어렵게 말할 것 없이 풀어쓰자면 아래와 같다.

- 7을 10번 곱했을 때 1의 자리 수는 얼마인가?

- 7, 9, 3, 1, 7, 9, 3, 1, 7, 9... 이처럼 1의 자리 수는 계속 반복되는 것을 알 수 있다.

- 우선 간단하게 구현해보자.

 

1. a에 a를 곱한 후, 10으로 나눠 나머지를 취한다.

2. b번 반복

 

코드

#include <stdio.h>

int main() {
	int T, a, b;
	scanf("%d", &T);

	while (T--) {
		scanf("%d %d", &a, &b);
		int c = a;
		while (--b) {
			c = c * a % 10;
		}
		printf("%d\n", c);
	}
}

 

결과

결과는 실패.

---

2. 두 번째 풀이 (마지막 풀이)

사고 과정

- 시간 초과면 모르겠는데, 단순 실패가 떴다. 적어도 예제 입력은 맞게 나왔다.

- 아,  a %= 10이 0인 경우를 놓쳤다. 이때 출력은 0이 나오지만, 실제론 10이 나와야 한다.

- 간단하게 고쳐서 테스트해봤다.

 

코드

#include <stdio.h>

int main() {
	int T, a, b;
	scanf("%d", &T);

	while (T--) {
		scanf("%d %d", &a, &b);
		a %= 10;
		int c = a;
		while (--b) {
			c = c * a % 10;
		}
		printf("%d\n", (c == 0 ? 10 : c));
	}
}

 

결과

다행히 성공... 문제를 너무 내 맘대로 해석했던 것 같다.

---

개선

실험 1

- scanf가 cin보다 빠르다는 건 알고 있었는데, 과연 얼마나 빨랐을까? 싶어 기존 iostream으로도 돌려보았다.

 

코드

#include <iostream>

int main() {
	int T, a, b;
	std::cin >> T;

	while (T--) {
		std::cin >> a >> b;
		a %= 10;
		int c = a;
		while (--b) {
			c = c * a % 10;
		}
		std::cout << (c == 0 ? 10 : c) << "\n";
	}
}

 

결과

익숙한 메모리 양. 메모리는 908 KB가 더 필요했고, 시간은 20ms 더 오래 걸렸다.

---

실험 2

사고 과정

- 연산량을 더 줄일 수 있는 방법이 있을 것 같은데. 이렇게 하면 어떨까?

- 0부터 9까지의 수는, 각각 일정한 수를 제곱하면 다시 처음 위치로 돌아온다.

- 각각 처음 원래 숫자로 돌아오는 횟수는 다르지만, 4개 주기로 원래 숫자로 돌아온다. (a의 1승, 5승, 9승...)

- 그러니, 많아도 4번 안에 정답을 구할 수 있다.

 

코드

#include <stdio.h>

int main() {
	int T, a, b;
	scanf("%d", &T);

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

		a %= 10;
		if (a == 0) {
			printf("10\n");
			continue;
		}

		b %= 4;
		if (b == 0) {
			b = 4;
		}

		int c = 1;
		while (b--) {
			c = c * a % 10;
		}
		printf("%d\n", c);
	}
}

 

 

결과

시간은 0 ms. 가장 빠른 방법이다.

---

가장 효율적인 코드

https://www.acmicpc.net/source/7379231

miryu님의 코드. 짧게 2문장으로 압축해두셨다.

내 코드와 비교

1. b를 줄일 때, b = (b - 1) % 4로 압축하셨다.

2. c의 초기 값은 a로 두셨다.

3. a를 한 자리수로 낮추진 않으셨다.

4. include가 아닌 import를 사용하셨다.

5. main 함수의 반환부를 아예 생략하셨다. (int main이나 void main이 아닌 그냥 main)

6. for 문의 내용없이, 초기식; 조건식; 증감식에서 모든 연산을 수행하셨다.

 

b = (b - 1) % 4로 압축하면 어떻게 작동할까?

예를 들어 b가 5라면, 위 연산 후 0이 된다. c = a가 이미 실행됐으니, 이는 a의 1승과 같은 효과다.

이후 (c - 1) % 10 + 1을 한다.

아. 이 부분은 10으로 나눌 때, 나머지의 범위를 0 ~ 9에서 1 ~ 10으로 바꾸는 역할을 한다. 이 부분을 해결하지 못 해 if문을 사용했었는데, 이런 방법이 있었구나.

다만 이 방법을 사용하려면, 나처럼 a %= 10으로 a를 한 자리로 줄이거나, c에 a를 곱할 때 % 10을 해선 안 된다. 한 번이라도 0이 된다면, 이후 출력에서 c 범위 설정이 이상해진다.

물론 연산 횟수가 적어진 만큼, 큰 문제는 되지 않을 것이다.

---

강평

아이디어엔 맞게 도착했지만, 정작 구현에서 많은 애를 먹었던 문제. 10으로 나눈 나머지를 1 ~ 10으로 고정시키는 법에 대해 배울 수 있었다.