1952. 수영장

static int price[4];
static int avail_days[12];

static int __solution(int d, int total)
{
	if (d >= 12)
		return total;
	else
	{
		int ret = __solution(d + 1, total + avail_days[d] * price[0]);
		int r1 = __solution(d + 1, total + price[1]);
		if (r1 < ret)
			ret = r1;
		r1 = __solution(d + 3, total + price[2]);
		if (r1 < ret)
			ret = r1;
		return ret;
	}
}

static int solution()
{
	for (int i = 0; i < 4; i++)
		scanf("%d", &price[i]);
	for (int i = 0; i < 12; i++)
		scanf("%d", &avail_days[i]);
	int ret = __solution(0, 0);
	if (price[3] < ret)
		ret = price[3];
	return ret;
}

모든 조합을 생각해보면 되는 문제다. 앞서 여러번 언급한 것 처럼, 최대, 최소 문제는 가급적 재귀를 이용하여 모든 경우를 다 찾아보는 것이 정확하다.

 

여기서 볼 만한 부분은 3개월치를 미리 끊었으면 3달 건너뛰어야 한다는 것이다.

그리고 성능을 좀 더 개선할 만한 부분이 있는데, 이는 예전에 작성했던 코드에 이미 있던 부분이다.

그 때에는 모든 경우를 고려하지 않고, 지름길을 찾으려 했던 때라 그렇게 작성되어 있던 것 같다.

 

방법은 한달치를 끊는 경우와 하루치를 여러개 끊는 경우는 해당 달에서 어느 것이 최소인지 바로 알 수 있다는 점이다.

이렇게 하면 재귀를 하나 줄일 수 있다.

 

 

//주의사항 및 정리

1. 일년치를 미리 결제하면 굳이 재귀를 돌면서 값을 비교하지 않아도 된다. 그러나 재귀가 반환하는 값과 비교는 해야한다. 처음에 이를 생각하였지만, 그 순간에 바로 코드에 어떠한 주석도 달지 않았다. 그래서 처음에는 실패를 하였다.

이 후 이를 재인지하여 맞추기는 하였다만 앞으로는 어떠한 생각이 나든지 그 생각을 주석으로 적어놓고, 확실한 경우에는 강력하게 어필하는 주석을 바로바로 달아야 겠다.