Codeforces Round #582 (Div. 3), (A,B,C) review

https://codeforces.com/contest/1213

Dashboard - Codeforces Round #582 (Div. 3) - Codeforces

먼저 풀었던 a, b, c 번 부터 리뷰하고 이후 문제는 아직 풀이를 제대로 하지 못해 이후에 리뷰하겠다.

---

풀이방법

 A. Chips Moving

 

 칩을 옮겨서 같은 곳에 두는 방법중 최소의 수를 찾는 문제다.

 먼저 조건을 잘보자.

조건

  잘 보면 홀수와 짝수인 개수를 세고 둘중에 작은 것의 개수를 구하는 문제라는 것을 알수있을것이다. 이후는 생략~

 

 

 B. Bad Prices

 

 이 문제는 지금 위치의 값보다 작은 값이 있는지 없는지 알아보는 문제이다.

 별건 없고 역순으로 MIN값을 만들어 비교하면 개수를 세면 끝이다.

 

 

 C. Book Reading

 

 이 문제는 완전탐색으로 풀기에는 시간이 말도 안되게 많을것이다. 그래서 끝자리는 0 1 2 3 4 5 6 7 8 9의 경우만 있고 /10마다 반복된다는 점에 착안해서 끝자리가 각각 0 1 2 3 4 5 6 7 8 9인 누적합 테이블을 미리 만들어 짰다. 자세하게 알고싶다면 밑의 코드를 참조하면 금방 알수 있을것이다.

#include <iostream>
#include <algorithm>

using namespace std;
long long sumTable[10][11];
long long n, m;
int q;

void sumTableInit()
{
	for (int i = 1; i < 10; i++)
		for (int j = 1; j < 11; j++)
			sumTable[i][j] = sumTable[i][j - 1] + ((i * j)%10);
}

void solve()
{
	long long lastNum = m % 10;
	long long divideNum = n / m;
	
	long long ans = sumTable[lastNum][10] * (divideNum / 10);
	ans += sumTable[lastNum][divideNum % 10];

	cout << ans << '\n';
}

int main()
{
	sumTableInit();
	cin >> q;
	for (int i = 0; i < q; i++)
	{
		cin >> n >> m;
		solve();
	}
	return 0;
}

---

 후기

 D번 두문제 풀고 리뷰하려고 했는데 시간안에 푸는 방법이 떠오르지가 않아 잊기전에 A, B, C번 먼저 올려둔다.