[ACM-ICPC][BOJ] 11504 - Wheel of Numbers 문제풀이

안녕하세요.

여행벌입니다.

오늘은 ACM-ICPC 2015 본선 문제인

BOJ 11504번 Wheel of Numbers 문제를 다뤄보겠습니다.

---

[문제해석]

N개의 부분으로 나뉜 원판이 있고, 숫자 X와 Y가 있다고 하자. ( X와 Y의 자릿수는 같고, M이라고 하자.)

원판의 부분을 순서대로 { K1, K2, ⋯ , Kn } 이라고 했을 때, 임의의 Ki부터 시계방향으로 M개의 숫자를 읽었을 때, 이 숫자가 X와 Y의 사이에 있는 숫자가 되는 경우를 계산해주는 알고리즘을 구현하라.

 

[알고리즘설계]

X, Y는 1 ~ 9 자리 숫자 중 하나이고, 원판의 조각 수는 1 ~ 100 개다.

다라서, 가장 많은 연산을 요하는 경우는 원판이 100개로 나뉘고, X, Y가 9자리 숫자인 경우이다.

그래 봤자 우리는 각각의 경우에 대해서 9개씩만 앞으로 순회하며 세어주고, X 와 Y 사이에 있는지만 체크해주면 된다.

즉, 무식하게 풀어도 되는 문제이다.

 

1. Input을 받는다. 이때, X, Y는 우리가 원하는 형태가 아니라, 자릿수마다 숫자를 입력받으므로 우리가 원하는 정수 X, Y로 바꿔준다.

2. X, Y의 자릿수만큼 원판이 저장된 배열을 다 순회하며 X와 Y 사이에 있는 값을 세준다.

#include<cstdio>

using namespace std;

int x[9];
int y[9];
int list[100];

int main(void) {
	int test_case;
	scanf("%d", &test_case); 

	for (int i = 0; i < test_case; i++) {
		// 입력받을게 참 많다...
		int ninput, length;
		scanf("%d %d", &ninput, &length);
		for (int j = 0; j < length; j++){
			scanf("%d", &x[j]);
		}
		for (int j = 0; j < length; j++){
			scanf("%d", &y[j]);
		}
		for (int j = 0; j < ninput; j++)
			scanf("%d", &list[j]);
		// X랑 Y를 int형으로 만들어주자.
		int X = 0, Y = 0, multiply = 1;
		for (int j = 0; j < length; j++) {
			X += x[length - 1 - j] * multiply;
			Y += y[length - 1 - j] * multiply;
			multiply *= 10;
		}
		int count = 0;
		// 순회하면서 count 해주자.
		for (int j = 0; j < ninput; j++) {
			int multiply2 = multiply / 10;
			int temp = 0;
			for (int k = 0; k < length; k++) {
				temp += list[(j + k) % ninput] * multiply2;
				multiply2 /= 10;
			}
			if (X <= temp && temp <= Y)
				count++;
		}
		printf("%d\n", count);
	}
}

예전 문제일수록 확실히 쉬운 것 같다.

---