[맛있는물회] <알고리즘> 2200번 "계산기 "

아주 간단한 그리디 알고리즘 문제이다.

 

문제 조건

---

다항식을 계산하기 위해 고안된 계산기가 있다. 이 계산기에는 0부터 9까지의 숫자와 +, ×(곱하기), x, =의 14개의 키가 있다.

예를 들어 이 계산기를 이용하여 x^3 + x + 11을 계산하려면 x, ×, x, ×, x, +, x + 1, 1, = 을 누르면 된다. 또 x^3 + 2x^2 + 11을 계산하기 위해서는 x, +, 2, ×, x, ×, x, +, 1, 1, = 을 누르면 된다.

일반적인 계산기라면 x, +, 2, ×, x, ×, x, +, 1, 1, = 을 x + 2x^2 + 11로 인식하겠지만, 이 계산기는 추가 메모리가 없기 때문에 계산을 할 때에 계산 직전에 계산기에 저장되어 있던 값에 계산을 한다. 즉 x, +, 2, ×, x, ×, x, +, 1, 1, = 을 입력하면 계산기에는 차례로 x, x+2, x^2+2x, x^3+2x^2, x^3+2x^2+11 이 입력되는 것이다.

문제를 단순하게 하기 위해서 최고차항의 계수는 항상 1이라고 가정하자. 또 음수 계수는 고려하지 않기로 하자.

다항식이 주어졌을 때, 이 계산기로 주어진 다항식을 계산하려면 계산기를 최소 몇 번 눌러야 하는지를 구하는 프로그램을 작성하시오.

 

Input

---

첫째 줄에 다항식의 차수 N(1≤N≤10,000)이 주어진다. 다음 줄에는 다항식의 계수가 최고차항부터 주어진다. 최고차항의 계수는 항상 1이며 모든 계수는 0 이상이다. 모든 계수는 1,000,000,000을 넘지 않는다.

 

 

Output

---

첫째 줄에 계산기를 누르는 최소 횟수를 출력한다.

 

 

생각한 아이디어

---

먼저 입력 값이 최고차항에서 부터 순서대로 내려오기 때문에 아주 간단하게 풀 수 있다. 최고 차항의 계수는 무조건 1이므로 값이 정해져있다.

1) 입력값의 차수가 0 즉, 상수값일때, 

2) 계수 값이 0이어서 무시해도 될 때,

3) 그 이외의 값인데 그 중에서도 계수가 1이어서 계수 부분을 무시해도 될 때와 계수값이 2 이상이어서 계수 값의 자리수를 찾아주어야 할 때로 구분하여서 풀이하였다.

아래의 소스코드의  if 문만 잘 확인한다면 간단하게 풀 수 있는 문제이다.

 

 

 

소스코드

#include 
using namespace std;

int main(void) {
	int n,i,j,cnt,num;
	cnt = 0;
	j = 0;
	cin >> n;
	for (i = n; i >=0; i--) {
		cin >> num;

		if (num == 0)
			continue;
		else if (i == 0) { // if input is constant, we have to divide the number as position of number.
			while (1) {
				if (num / 10 != 0) {
					cnt++;
					num /= 10;
				}
				else {
					cnt++;
					break;
				}
			}
			break;
		}
		else {
			if (num == 1) {// if number is '1', we can skip the process that muliplicate the Coefficient
				cnt += i + (i - 1);
			}
			else {//If Coefficient is not the single digit, we have to count
				while (1) {
					if (num / 10 != 0) {
						j++;
						num /= 10;
					}
					else {
						j++;
						break;
					}
				}
				cnt += (j+1) + i + (i - 1);
				j = 0;
			}
		}
		cnt++; //It means that counting the '+'
	}
	cnt++; //We must count the '='

	cout << cnt;
	return 0;
}